数学的帰納法

定義

数学的帰納法は、性質 $P(n)$P(n) がある番号 $n_0$n0​ 以上のすべての整数について成り立つことを、たった二つの確認によって証明する。

この二点が無限個の命題を打ち立てる。そこに力がある。確かめるのは一つの場合と一つの含意にすぎない。

ひとつの比喩と、その限界

ドミノの列。最初の一枚を倒し、どの一枚も次を倒すと保証すれば、すべてが倒れる。

比喩は仕組みについては正しく、及ぶ範囲については誤っている。ドミノの列は有限であり、倒れるには時間がかかる。帰納法は無限個の番号にかかわり、時間のなかで進行しない。伝播を語るのではなく、性質を証明するのである。

最後まで運んだ例

最初の $n$n 個の整数の和が $\dfrac{n(n+1)}{2}$2n(n+1)​ であることを示す。

基底。 $n = 1$n=1 のとき、和は 1 であり、$\dfrac{1 \times 2}{2} = 1$21×2​=1。

帰納段階。 番号 $n$n で公式が成り立つとする。すると：

$1 + 2 + \dots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$1+2+⋯+n+(n+1)=2n(n+1)​+(n+1)=2n(n+1)+2(n+1)​=2(n+1)(n+2)​

これは番号 $n+1$n+1 における公式である。二段階とも成り立つので、性質はすべての $n \geq 1$n≥1 について成り立つ。

二つの段階はどちらも欠かせない

帰納段階だけでは何も証明できない。$P(n)$P(n) を「$n = n + 1$n=n+1」としよう。

この性質は遺伝的である。$n = n+1$n=n+1 ならば、両辺に 1 を足して $n + 1 = n + 2$n+1=n+2。一歩は申し分なく伝わる——そして性質はすべての整数について偽である。それを始める番号がひとつもないからである。

基底だけでも足りない。1 で真であり、その先で偽になる性質もありうる。

強い帰納法

証明によっては直前の番号だけでは足りない。強い帰納法は $n$n ひとつではなく、$k \leq n$k≤n なるすべての $k$k について $P(k)$P(k) を仮定する。

一歩がずっと前の番号を必要とするときに使う。整数を素因数に分解する場合、参照するのは直前ではなく、任意により小さい二つの因数である。

まとめ

出発点と伝わる一歩が無限個の場合を証明する。そのどちらも省けない。