数学的帰納法の原理と証明の手順

数学的帰納法は、自然数 $n$ に関する命題を証明するための方法である。

証明の手順

命題「すべての自然数 $n$ について $P(n)$ が成り立つ」を証明するには、以下の2段階を示す。

この2つが示されれば、$P(1),P(2),P(3),\dots$ がすべて成り立つ。

原理の説明

基底で $P(1)$ が成り立つ。帰納で $P(1)\Rightarrow P(2)$ なので $P(2)$ が成り立つ。同様に $P(2)\Rightarrow P(3)$、$P(3)\Rightarrow P(4)$、… と無限に続く。ドミノ倒しのようなイメージである。

例題1

$1+2+3+\cdots +n=\frac{n(n+1)}{2}$ を証明せよ。

基底：$n=1$ のとき、左辺 $=1$、右辺 $=\frac{1\cdot 2}{2}=1$。成立。

帰納：$n=k$ で成立を仮定する。すなわち $1+2+\cdots +k=\frac{k(k+1)}{2}$。

$n=k+1$ のとき、

$$1+2+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}$$

これは $n=k+1$ での公式に一致。よって成立。

以上より、すべての自然数 $n$ で成り立つ。

出発点が1でない場合

$n\ge 2$ や $n\ge 0$ から始まる命題では、出発点を変える。$n\ge 3$ で成り立つ命題なら、$P(3)$ を基底とする。