数学的帰納法

「n=1 で成立し、n=k で成立すれば n=k+1 でも成立する——ゆえにすべての自然数 n について成立する」。数学的帰納法のこの論理構造は、無限個の命題をたった二つのステップで証明する。ドミノ倒しの比喩が有名だ——最初の牌が倒れ、倒れた牌が次を倒せば、無限のドミノはすべて倒れる。しかしこの比喩が捉えきれない「跳躍」が、数学的帰納法の本質にある。

結城浩が対話で示した直感と厳密さ

数学ガールで結城浩は、数学的帰納法を高校生のキャラクターの対話を通じて腹落ちさせた。「n=k で成立するとき n=k+1 でも成立する」という「帰納的ステップ」は、実際にはどんな k についても成立することを証明しなければならない。これは「k という特定の数について確認する」のではなく、「k を任意の自然数として論じる」という汎用的な論証だ。直感的には「個別の確認」なのに、実際には「すべてに適用される証明」——この微妙なギャップを乗り越えることが、数学的帰納法の理解の核心だ。テトリス、組み合わせの公式、ド・モアブルの定理——様々な命題を帰納法で証明する過程で、命題の構造を「帰納的に読む力」が培われる。

帰納法の種類と応用範囲

数学的帰納法には基本形の他に「強い帰納法」がある。基本形は n=k のときに成立すれば n=k+1 も成立することを示す。強い帰納法は「n=1 から n=k まですべて成立するとき、n=k+1 も成立する」ことを示す。フィボナッチ数列のように「前二項」に依存する数列の性質を証明するには、強い帰納法が必要になる。また「整礎帰納法」と呼ばれるより一般的な形式もあり、自然数以外の「整礎な順序関係」に対しても帰納法の論理が適用できる。計算機科学での再帰的アルゴリズムの正当性証明は、帰納法の論理と同一構造を持つ。プログラムの停止性証明、データ構造の操作の正確性——帰納法は純粋数学を超えて情報科学の基盤でもある。

証明の美しさと限界

数学的帰納法の美しさは、有限の論証で無限を扱うことにある。しかし限界もある。「帰納的ステップ」を証明することが、問題の本質的な難しさを含む場合が多い。また自然数について成立することが、整数全体・実数・複素数では成立しないことも多い。数学の美しさの一つは、こうした「証明の射程」を正確に理解することにある——どのツールが何を証明でき、何を証明できないかを知ること。生成関数という別のアプローチは、帰納法とは異なる視点から数列の性質を解明する。複数の証明方法が同じ命題に到達するとき、それぞれの証明が異なる数学的構造を照らし出す。

数学的帰納法の哲学的深み

数学的帰納法は単なる証明技法を超えた哲学的問いを含んでいる。無限に多くの命題（n=1, 2, 3, …について成り立つ）をすべて証明することは、文字通りには不可能だ。数学的帰納法は「最初の一歩（n=1）が成り立ち、一歩が成り立てば次の一歩も成り立つ」という有限の証明から、無限の真実を確定するという飛躍を含む。この飛躍は論理的に正当化されるが、「無限を扱う」という数学の本質的な性格を示している。

帰納法の「累積帰納法」や「整礎帰納法」への拡張は、標準的な帰納法が直接適用できない問題を解くための理論的深化だ。また情報科学では「プログラムの正しさの証明」に帰納法が使われる——繰り返し処理が終了するかどうか（停止性問題）の証明は、一種の帰納的論証を用いる。チューリングが示した「停止問題は決定不可能」という定理は、帰納的証明の枠組みが適用できない問いの存在を示す。

数学的帰納法はフィボナッチ数列や素数に関する多くの定理の証明で中心的な役割を果たす。生成関数による分析は帰納的な関係式（漸化式）を解析的に扱う強力な補完的アプローチを提供する。数学の美しさにおいて、数学的帰納法は「限られた手段から無限の真実を引き出す」という数学的思考の優雅さを体現している。