next up previous 次: 変形型数学的帰納法 上: 論証の推進 前: 考え方

数学的帰納法

数学的帰納法の原理

「数学的帰納法」はよく知っている言葉だが, ではその中にある「帰納」とはどういう意味なのだろうか. 「帰納」は「演繹」という言葉と対になっている. 「帰納」とは多くの例を調べその間になり立つ法則を推測して きっとこうに違いなという「仮説」を立てることだ. 「演繹」は,成立することがわかっている一般的な命題をもとに, 具体的,個別的な命題を推論によって証明することをいう.

では「数学的帰納法」とは何か. 自然数を含む数学的事柄がどのようになっているかを知りたいとき,

(1)
1のときはこうだ,2のときはこうだと調べていって
(2)
$n$ のときもこうに違いないと推測して仮説を立て,
(3)
$n=1$ で成立する. $n=k$ で成立すれば $n=k+1$ でも成立する. ゆえに任意の $n$ で成立することを証明する.
というのが普通のやり方だ. この(3)の部分の証明方法のことが「数学的帰納法」である. このような証明法が可能な根拠は自然数の次の性質による.

自然数の部分集合$A$が次の性質をもっているとする.

\begin{displaymath}
1\in A,\ かつ\ k\in A\Rightarrow k+1 \in A
\end{displaymath}

このとき集合$A$は自然数の集合$Z$と一致する.
数学的帰納法では$A$は命題の成立する番号の集合である. $A$が上の性質が成り立つことを示すことで, $A$が自然数の全体に一致し, したがってすべての自然数でその命題が成立する, これが数学的帰納法の原理だ.

入試問題では,(1)〜(3)全体が問題になることもあれば, 仮説は提示して(3)の部分の論証だけが問題になることもある. この(3)の部分の証明法は,この通りの形である必要はなく, いくつかの応用形がある.まずそれを確認しよう.

$p(n)$ を自然数 $n$に関する条件とする.

「すべての自然数 $n$に対し条件$p(n)$ が成立する」 ことを証明する方法としての数学的帰納法の主な型は次の三つである.

  1. [基本型]
    1. $p(1)$が成立する.
    2. $p(k)$が成立するなら$p(k+1)$が成立する.
    3. (1), (2)より, すべての $n$ に対して $p(n)$が成立する.
  2. [応用型1]
    1. $p(1),\ p(2)$が成立する.
    2. $p(k-1),\ p(k)$が成立するならば$p(k+1)$が成立する.
    3. (1), (2)より, すべての $n$ に対して $p(n)$が成立する.
  3. [応用型2]
    1. $p(1)$が成立する.
    2. $p(1),\ p(2),\ \cdots,\ p(k)$が成立するなら$p(k+1)$が成立する.
    3. (1), (2)より, すべての $n$ に対して $p(n)$が成立する.
いずれの型で証明しようとしているのか,はっきりさせて論述しなければならない.

Aozora Gakuen