数学的帰納法と自然数の和の証明

無限に多くの自然数についての主張を、一つずつ計算して確かめることはできません。数学的帰納法では、出発点が正しいことと、正しさが次へ伝わることを示します。自然数の和を例に、仮定をどこで使うかまで追います。

成立する条件

添字は正整数です。$n=0$ を含める場合は、空の和を $0$ と定め、出発点も $0$ にします。

帰納段階では、特定の $k$ だけでなく任意の $k\ge1$ を扱います。結論を無条件に仮定するのではなく、$P(k)$ を仮定したときに $P(k+1)$ が導けることを証明します。

証明

1. まず $n=1$ では左辺が $1$、右辺が $1\cdot2/2=1$ となり、出発点は成立します。
2. 次に、ある任意の正整数 $k$ について $1+\cdots+k=k(k+1)/2$ が成り立つと仮定します。$k+1$ 番目までの和は、そこまでの和に新しい項 $k+1$ を足したものです。
3. 帰納法の仮定を代入すると、$$1+\cdots+k+(k+1)=\frac{k(k+1)}2+(k+1)=\frac{(k+1)(k+2)}2.$$ これは公式の $n$ を $k+1$ に置き換えた式です。よって帰納段階が成立します。
4. 出発点から帰納段階を繰り返すと、$1,2,3,\ldots$ のどの段階にも到達できます。自然数の整列性を使えば、反例があると仮定して最小の反例 $m$ を取り、$m\ne1$ かつ $P(m-1)\Rightarrow P(m)$ となる矛盾としても説明できます。

使ってみる

$1+2+\cdots+100=100\cdot101/2=5050$ です。$1$ から $100$ まで実際に足すことは、この一例の確認にはなりますが、任意の $n$ についての証明にはなりません。

数列の不等式や漸化式の一般項にも同じ枠組みが使えます。帰納段階で式が閉じない場合は、証明したい主張をより強い形にする必要があることもあります。

注意点

帰納段階だけでは出発点がありません。例えば「全自然数が負である」という誤った主張も、前提が偽なら条件文を形式上満たす場合があります。基底と帰納段階の両方が必要です。

関連項目