数学的帰納法って何!?

月刊ホームページ2005年11月号 (数理システム構造講座)

みなさんは、数学的帰納法を知っていますか？数学的帰納法は、数学の定理を証明する1つの方法です。定理を証明するなんて嫌い！数学的帰納法なんて難しい！と言っている人はいませんか? 実は、この数学的帰納法は、思ったほど難しくありません。そして、数学的帰納法を覚えることで定理を楽しく証明することができます。

では、まず自然数の集合{1,2,3,...}を頭に思い浮かべてください。
眠れない夜は、羊を数えますね羊が1匹、羊が2匹、... これでどーして眠れるかというといつまでも数えることができるからです。もし、途中で自然数が終わってしまったら、そこで羊を数える作業が出来なくなります。するとまた余計なことを考え初めて眠れなくなってしまいます。単調な動作を際限なく繰り返しているからこそ、眠くなるわけで、自然数が無限に続くおかげで、私達は安心して羊を数え続けられるわけです。

数学的帰納法はこの自然数達を上手に使って数学の定理を証明します。
ですから数学を定理を証明するときは、小さいところから順にやっていって何回か続けて行くうちになんだか眠くなって来たら、数学的帰納法の出番なのです。例えば次の定理はどうでしょうか？

「3円と5円の切手を持っていれば8円以上のどんな郵便料金も払える」

えー! 証明できないよー!!!と言うかも知れませんね。いきなり、ズバっと解こうとすると無理があります。では、

「3円と5円の切手を持っていれば8円の郵便料金も払える」

ならどうでしょうか? とっても簡単ですね。3円切手1枚、5円切手1枚を使えば良いわけです。では、

「3円と5円の切手を持っていれば9円の郵便料金も払える」

ならどうでしょうか? これも簡単ですね。3円切手3枚を使えば良いわけです。では、

「3円と5円の切手を持っていれば10円の郵便料金も払える」

ならどうでしょうか? これもまた簡単ですね。5円切手2枚を使えば良いわけです。では、

「3円と5円の切手を持っていれば11円の郵便料金も払える」

ならどうでしょうか? えー!?とでもさっき 8円は作れましたから、 11円は8円足す3円つまり、11 = 8 + 3 = 3+5 +3で、 3円切手2枚、5円切手1枚を使えば良いわけです。では、

「3円と5円の切手を持っていれば12円の郵便料金も払える」

ならどうでしょうか? またまた簡単ですね、 3円切手4枚を使えば良いわけです。では、

「3円と5円の切手を持っていれば13円の郵便料金も払える」

ならどうでしょうか? さっき10円は作れましたから、 13 = 10+3 = 5+5 +3で良いわけで、3円切手1枚と5円切手2枚を使えば良いわけです。では、

「3円と5円の切手を持っていれば14円の郵便料金も払える」

ならどうでしょうか? さっき11円は作れましたから、 14 =11+3 = 3+5+3 +3で良いわけで、3円切手3枚と5円切手1枚を使えば良いわけです。

あれ、こんなこといつまで続けたら良いのでしょうか？人生は短いしさっさとこんな定理を片付けたい気がしますよね。そこで、いままでの結果をちょっと式にしてみましょう。


  8 = 3+5
  9 = 3+3+3
 10 = 5+5

 11 = 3+5   + 3
 12 = 3+3+3 + 3
 13 = 5+5   + 3

 14 = 3+5   + 3+3
 15 = 3+3+3 + 3+3
 16 = 5+5   + 3+3

 17 = 3+5   + 3+3+3
 18 = 3+3+3 + 3+3+3
 19 = 5+5   + 3+3+3

......

だんだん眠くなって来ませんか? これこそ羊が1匹、羊が2匹... です。もう見えて来ましたか？同じ事の繰り返しが始まりましたね。当り前ですが、郵便料金 △円を支払うことが出来れば、 3円切手をもう1枚使って、△＋3 円を支払うことが出来ます。よって、8円, 9円, 10円を支払えれば、もう8円以上のすべての郵便料金を支払うことが出来るわけです。まとめると、

8円, 9円, 10円を支払う事が出来ることを証明する。(簡単!)
△円を支払うことが出来れば、 △＋3 円を支払うことが出来る事を証明する。
(3円切手をもう1枚使えばよいエッヘン!)

これで、 8, 9, 10, 11=8+3, 12=9+3, 13=10+3, 14=11+3, 15=12+3 ... とすべての料金を支払うことが出来ると証明できました。

基本は、小さいところから眠くなるまで繰り返しやってみる事です。

もう1つ問題を紹介します。折紙を縦と横に2つ折、4つ折、8つ折と折ってみましょう!。その折紙を広げるとたくさんの正方形が出来ます。

縦と横に2つ折なら、4個

縦と横に4つ折なら、16個

縦と横に8つ折なら、64個の正方形が出来ますね。

このうち1つの正方形を黒く塗りつぶします。
このとき、残った正方形を、3つの正方形で出来た「L字型プレート」

できれいに埋めることが出来ることを証明しましょう！
ちょっと数学的に定理にすると...

縦横を2ⁿ等分した正方形の中の小さい1つの正方形を適当に塗りつぶすと、
残った小さい正方形 2^2ⁿ-1個を「L字型プレート」できれいに埋めることが出来る。

では、縦と横に2つ折で左下を黒く塗りつぶしましょう。

これは、簡単ですね。

次に、縦と横に4つ折で、上から2番目、左から3番目を黒く塗りつぶしましょう。

これも出来ましたか？

次に、縦と横に8つ折で、上から6番目、左から3番目を黒く塗りつぶしましょう。

これも出来ましたか？

さて、いろいろな場所を黒く塗りつぶしてやってみましょう。眠くなって来たら、帰納法を使うチャンスですよ!

今回のお話は、
コンピュータサイエンスのための 離散数学入門
C.L. Liu (著), 成嶋 弘 (翻訳), 秋山 仁 (翻訳)
オーム社 ; ISBN: 427413007X ; (1995/03)
から例題を使わせていただきました。
とても面白い本なので、機会があったら是非呼んでください。