2011/06/01

数学的帰納法

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

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

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

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


数学的帰納法には、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) = n2

上記の問題の式(述語)をP(n)とします。
述語P(n): 1 + 3 + 5 + … + (2n-1) = n2

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

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

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


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

まずは、自然数kについて、仮にP(k)が成り立つと仮定します。
P(k): 1 + 3 + 5 + … + (2k-1) = k2
この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)2
ここでもまだ成り立つと言っているわけではありません。ただ、この式(命題)P(k+1)が成立するか確かめたい、いわば目標です。

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

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

P(k+1)の左辺は、
1 + 3 + 5 + … + (2k-1) + {2(k+1)-1} (下線部に仮定Kを使って)
= k2 + {2(k+1)-1} (計算して)
= k2 + (2k+2-1) (計算して)
= k2 + 2k +1 (因数分解すると)
= (k+1)2

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

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

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


ステップ(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)が成り立つ」と言えます。

ブログ アーカイブ