数列・Σ・漸化式・帰納法
「 で成り立つ」と「 で成り立つなら でも成り立つ」の つを示せば、すべての自然数 で成り立つ、といえる証明法。
自然数 についての主張 を、すべての で一気に確かめるのは大変だよね。そこで 段がまえで示すのが数学的帰納法だ。 出発点として が成り立つこと、 どこか つ が成り立つと仮定すると、その次の も必ず成り立つこと。この つがそろえば、 から 、 から … と連鎖して、どんな大きな にもたどり着ける。ドミノで言えば、 最初の 個が倒れ、 どれかが倒れたら次も倒れる、なら全部倒れる、と同じことだよ。無限にある主張を、たった つのことを示すだけで全部証明できる。これがこの方法のいちばんの値打ちだね。
出発点(基底) が成り立つこと。「 が成り立つ」を仮定したうえで を導けること。この仮定 を帰納法の仮定とよび、 の証明では必ずこれを使うのがコツだよ。出発点は とは限らず、 から始めれば「 のすべてで成り立つ」が示せる。
なぜ つを示すだけで「すべての 」に届くのかを、ドミノの連鎖でたどる。どんな も、出発点 から 段ずつ必ず到達できることを確かめる。
ねらう を つ決める(たとえば )。 より は成り立つ。これが連鎖の最初のドミノだよ。
は「成り立つ つの次も成り立つ」という橋渡し。 が成り立つから が成り立ち、 から 、… と 段ずつ確実に進める。
この橋を 回わたれば、決めておいた にちょうど着く。 はどんな自然数でもよかったから、結局すべての で が成り立つ、というわけだね。
ポイントは、無限個の主張を つずつ確かめたのではなく、 出発点と 次へ伝わる仕組みの つだけで「どこにでも到達できること」を保証した、ということ。これが数学的帰納法の心臓部だよ。
いちばんのつまずきは の出発点を忘れること。 の「次へ伝わる」だけ示しても、最初の 個が倒れなければドミノは一つも倒れない。連鎖には必ず出発点がいる。逆に だけで がなければ、 が言えるだけで先へ進めない。両方そろって初めて全部に届くんだ。もう つの注意は、 で帰納法の仮定 をちゃんと使うこと(使わずに証明できたなら、それは帰納法を使う必要がなかった主張)。なお で「 から まで全部成り立つ」と仮定してよい強い帰納法もあり、漸化式や場合分けの証明で役に立つよ。
言葉で読んだら、動くアニメと自分の手で確かめてみよう。
この定理が、実際の問題でどう効くのかを見てみよう。