数学的帰納法 mathematical induction とは, 自然数に関する証明法である。 屡々省略して帰納法と呼ばれる。
自然数 n を含んだ定理のようなもの --- それを命題 predicate というが --- P(n) を考える。 例えば, 1 + 2 + 3 + … + n = n(n+1)/2 というのが P(n) である。
これの証明を次のように行う。
[1] P(1) が正しいことの証明。
[2] P(k) が正しいことを仮定 (induction hypothesis)。
[3] P(k) を用いて P(k+1) を証明 (induction step)。
あんまり納得いかないだろうから, 実際に上の式でやってみよう。
P(n): 1 + 2 + 3 + … + n = n(n+1)/2 とする。
[1] P(1) とは左辺が 1 だけ, 右辺は n = 1 を代入して 1×2/2 = 1 だから, 正しい。
[2][3] にいく前に, P(1) を用いて P(2) を証明しよう。 即ち
左辺 = 1 + 2 = 1×2/2 + 2 = (1×2 + 4)/2 = 2(1 + 2)/2 = 2×3/2 = 右辺。
同様にして P(2) を用いて P(3) を証明すると
左辺 = 1 + 2 + 3 = 2×3/2 + 3 = (2×3 + 6)/2 = 3(2 + 2)/2 = 3×4/2 = 右辺。
では [2] を確認しておこう。 [2] とはこの場合
P(k): 1 + 2 + 3 + … + k = k(k+1)/2
であり, これが正しいと仮定するのである。 今までのように, P(1) が正しいことを証明して P(2) を証明し, P(2) が正しいと証明されたので, それを用いて P(3) を証明し, ...... と順にやっていって, P(k) のところまで順に証明されたと思うのである。 こうして, その次の数 P(k + 1) で証明されれば, 結局, n が幾つであっても, そこまで --- 原理的には --- 順順に証明を積み重ねていけば証明できる, というのが数学的帰納法である。
実際の P(k + 1) の証明は
左辺 = 1 + 2 + 3 + … + k + (k + 1) = k(k+1)/2 + (k + 1)
= (k(k+1) + 2(k+1))/2 = (k + 1)(k + 2)/2 = (k + 1)((k + 1) +1)/2 = 右辺。
これで証明された。
尚, 今のようにするのが本式であるが, [2] を書くのを省略して P(n + 1) を証明する方法もよく取られる。 これは略式なので, 簡易帰納法と呼ばれている。
準備の目次へ。