数学的帰納法

久しぶりに『数学ガール』で数学的帰納法のやり方を見ました。

「帰納」とは、ひとつひとつの具体的なことから一般的な原理を引き出すこと。

「帰納」の逆の意味として「演繹」という言葉があり、「演繹」は、一般的な原理からひとつひとつの事柄を推論することです。

「数学的帰納法」は、証明の方法のひとつで、「どんなとき（大体は「任意の自然数」）でも～が成り立つ」ということを証明する方法としてよく使用されます。


数学的帰納法には、2つのステップがあります。

自然数nに関する述語P(n)について、

ステップ(a)：P(1)を証明する
ステップ(b)：どんな自然数kに対してもP(k)が成り立つならば、P(k+1)も成り立つことを証明する

という2つのステップです。

この2つの証明ができれば、自然数nに関する述語P(n)は、どんな自然数でも成り立つことが証明できます。



例えば、これも『数学ガール』に出てきた例です。

問題：
任意の自然数nについて、以下が成り立つことを証明せよ。

1 + 3 + 5 + … + (2n-1) = n²

上記の問題の式（述語）をP(n)とします。

述語P(n)：　1 + 3 + 5 + … + (2n-1) = n²

まずは、ステップ(a)として、P(1)を証明します。P(1)というのは、n = 1 のときです。

n = 1のとき、P(n)の左辺は「1」、右辺も1の2乗なので「1」。

つまりP(1)は「1 = 1²」なので成立します。


次にステップ(b)です。

まずは、自然数kについて、仮にP(k)が成り立つと仮定します。

P(k)：　1 + 3 + 5 + … + (2k-1) = k²

このP(k)が成り立つというのは、あくまで「仮定」です。成り立つかどうかはまだわかっていません。この式をとりあえず仮定Kとしましょう。

次にP(k+1)について確認してみます。

P(k+1)というのは、n = k+1 のときなので、P(n)のnの部分に k+1 を入れると以下のようになります。

P(k+1)：　1 + 3 + 5 + … + (2k-1) + {2(k+1)-1} = (k+1)²

ここでもまだ成り立つと言っているわけではありません。ただ、この式（命題）P(k+1)が成立するか確かめたい、いわば目標です。

そこで、命題P(k+1)の左辺部分を計算してみましょう。左辺部分は「1 + 3 + 5 + … + (2k-1) + {2(k+1)-1}」です。

これを計算するために、先ほど成り立つと仮定した仮定Kを使います。仮定Kとは、「1 + 3 + 5 + … + (2k-1) = k²」です。

P(k+1)の左辺は、

1 + 3 + 5 + … + (2k-1) + {2(k+1)-1} （下線部に仮定Kを使って）
= k² + {2(k+1)-1}　（計算して）
= k² + (2k+2-1)　（計算して）
= k² + 2k +1　（因数分解すると）
= (k+1)²

これは、P(k+1)の右辺と同じです。

なので、ステップ(b)では、次のことが証明されました。「P(k)が成り立つならば、P(k+1)も成り立つ」

ステップ(a)(b)両方揃って、「任意の自然数nについて、1 + 3 + 5 + … + (2n-1) = n² が成り立つ」が証明できた、と言えます。


ステップ(b)の証明だけだと、「P(k)が成り立つならば、P(k+1)も成り立つ」ということが証明できただけです。P(k)が成り立たなければ、意味のない命題になってしまいます。

具体的にいうと、ステップ(b)で証明したことは、

P(1)が成り立つならば、P(2)が成り立つ
P(2)が成り立つならば、P(3)が成り立つ
P(3)が成り立つならば、P(4)が成り立つ
P(4)が成り立つならば、P(5)が成り立つ
……
P(k)が成り立つならば、P(k+1)が成り立つ

ということを証明しました。

ここにステップ(a)での、P(1)は成り立つことを証明していることが生きてきます。

つまり、

P(1)が成り立つので、P(2)が成り立つ
P(2)が成り立つので、P(3)が成り立つ
P(3)が成り立つので、P(4)が成り立つ
P(4)が成り立つので、P(5)が成り立つ
……
P(k)が成り立つので、P(k+1)が成り立つ

したがって、「任意の自然数nにおいて、P(n)が成り立つ」と言えます。