数学的帰納法は大丈夫なのだ

高校時代の私は数学的帰納法に関して「怪しいというか，無意味なことしてんじゃないの？　成り立つことがわかってるときにしか使えないのでは」と思っていた．

クラスの友人にこのことを説明しても，あまり関心がなさそうで，取り合ってもらえなかった．

今となっては自分なりに納得しているわけですが，当時の自分に納得してもらえるように説明を試みようというのが今回のテーマです．

数学的帰納法とは

一応復習しておきます．

自然数 $n$ に関する命題について，

• $n=1$ のとき，命題は成り立つことを証明する．
• 任意の自然数 $k$ に対して，$k$ のとき命題が成り立つと仮定すると，$k+1$ のときも命題が成り立つことを証明する．

• このとき，すべての自然数 $n$ に対して，命題は成り立つ．

以上の手順の証明法を数学的帰納法といいます．

私が使っていた教科書には上のように書いてありました．

高校時代の私はどの辺に疑問を感じたのか

• 「任意の $k$ に対して正しいと仮定する」とはどういう意味か？　$k$ が任意であれば，その $k$ の中に $k+1$ も入っているのではないか．それなら命題はすべての自然数に対して成り立つことを仮定していることになり，「命題が成立するなら命題は成立する」の証明という無意味なことをしようとしているのではないか？

• $1,2,3,\dots$ と調べてみて正しそうな命題にしか使えないのではないか．

• そもそも，$k$ のとき正しくて，$k+1$ のときに正しくない命題など存在するのか？

解説しよっか

以下，命題を $P$ であらわし，自然数 $n$ に対する命題 $P$ を $P(n)$ とあらわすことにしよう．

多分こんな説明

今ならあの頃の自分にこういうふうに説明する．

命題が成り立つことを確認しなければならないのは，$P(1)$ だけである．$k\geqq 2$ の場合は気にしなくてよい．

次に任意の自然数 $k$ に対して「 $P(k)\Rightarrow P(k+1)$ 」を証明する．「 $P(k)\Rightarrow P(k+1)$ 」はこの塊がひとつの命題である．

$P(k)\Rightarrow P(k+1)$ の証明の手順はどうであるか．それは

$P(k+1)$ を証明する．ただし $P(k)$ を用いてよい．

である．

ということで，上で書いた数学的帰納法を以下のように言い替える；

• $P(1)$ が成り立つことを証明する．
• 任意の自然数 $k$ に対して，$P(k)\Rightarrow P(k+1)$ が成り立つことを証明する．

• このとき，命題 $P$ はすべての自然数 $n$ に対して成り立つ．

付帯説明

高校時代のアイツは上の説明で分かるはずがないから，さらに説明を加える．

数学的帰納法

まず，なぜ数学的帰納法みたいな証明法が存在するのかについて．

自然数 $1,2,\dots,n,\dots$ に対して，命題 $P$ が成り立つかどうかは，$P(1),P(2),\dots,P(n),\dots$ に関して順番に確かめていけばそれで良いのだが，それでは確認作業が有限回のステップでは終わらない．証明は有限の長さでなければならない．

「以下同様に」では証明したことにはならない．

という事情を鑑みれば，まあ数学的帰納法かなって気がしてくるだろ？

一つ目の疑問

一つ目の疑問は

• 「任意の $k$ に対して正しいと仮定する」とはどういう意味か？　$k$ が任意であれば，その $k$ の中に $k+1$ も入っているのではないか．それなら命題はすべての自然数に対して成り立つことを仮定していることになり，命題が成立するなら命題は成立するということを証明しようとするという無意味なことをしようとしているのではないか？

でしたね．

「任意の自然数 $k$ に対して」というとき，これは「自然数の中からひとつを選んで固定する．その固定した自然数を $k$ とする」という意味だ．

あのときのお前は「任意の $k$ について $P(k)$ 正しいと仮定した． $k$ は任意であったから自然数であれば何でもよいはず．だったら，$k+1$ のときも $P(k+1)$ は成り立つと仮定してよい」と考えていたようだ．そうだな？　でもそうじゃないんだ．

教科書に書いてあった

任意の自然数 $k$ に対して，$k$ のとき命題が成り立つと仮定すると $\dots$

という文言を誤解したお前が悪いのだ．でもまあ気にするなドンマイ．

その部分は

• 任意の自然数 $k$ に対して，$P(k)\Rightarrow P(k+1)$ が成り立つことを証明する．

とかくべきだった．$P(k)$ が実際に成り立つか否かはどうでもいいのだ．

数学的帰納法が主張しているのは，$P(k)$ と $P(k+1)$ の間に関連があるのか否かである．

各々が独立に正しいかどうかは具体的に確かめれば分かる．ただ，確認すべきはそこではなく，自分（ $P(k)$ ）と自分の後者（ $P(k+1)$ ）との間に関連があるかどうかなのだ．

例えて言うなら $\dots$ 山脈の各山の頂上には，確認した限り，ふもとの登山口から登山道が通じていて登れることは分かっている．それはそれとして，山頂から隣の山頂へ尾根伝いに道が付いているかどうかを知らなければならない —— ということだ．

二つ目の疑問

二つ目の疑問は

• $1,2,3,\dots$ と調べてみて正しそうな命題にしか使えないのではないか．

でしたか．

この「正しそうな命題にしか使えないのでは？」という疑問に対しては，「正しそうな命題に使えます」というのが答えになるか．

正しくなさそうな命題を数学的帰納法で証明しようとすれば，ちゃんと否定的な結果が出るので心配ない．例えば，自然数 $n$ に対して，

$1+2+\dots+n=n^2$

なる数式が成り立つか否か．実際に確かめれば分かるが，一般にはこの等式は成り立たない．数学的帰納法でこの式の証明を試みてみる；まず，$n=1$ のときは成り立つ．しかし，任意の自然数 $k$ に対して

$1+2+\dots+k=k^2\Rightarrow 1+2+\dots+k+(k+1)=(k+1)^2$

が成り立つかというと，成り立たない．

三つ目の疑問

三つ目の

$k$ のとき正しくて，$k+1$ のときに正しくない命題など存在するのか？

という疑問に対しては，

知るかそんなもん！

ということでわはは．

まとめ

いかがでしたか．　と，このように説明を試みてみました．

まあ語弊を承知で簡単に言えば，

命題が正しいのは確かめていけばわかるけど，それでは有限の長さで終わらないから証明ではない．証明する必要はあるが，有限の長さで証明しようと思ったら数学的帰納法なのね．

あと，「 $k$ のとき成り立つ」ではなくて，「 $k$ のとき成り立つと仮定する」だよー．

ソースはワイ

こんな感じじゃないでしょうかと．

納得したか？　高校時代のオレ．

ていうか，高校時代の自分の数学がどのぐらいのレベルだったかなんて今さら思い出せるわけねーだろーが！

ブログ村ランキング参加中
クリック↓してもらえると励みになります．

にほんブログ村
Amazonにて「素朴集合論」販売中です（Kindle版）．製本版は販売休止中スマン．

Views: 302