最初のドミノを倒し、倒れたものが次を倒す――すると全部倒れる。
すべての正の整数に対して一度に命題を証明したいとしよう――たとえば1 + 2 + ⋯ + n = n(n+1)2が n = 1 でも、n = 100 でも、n = 10億でも、例外なく成り立つことを。一つ一つ確認することはできない。無限にあるから。最初のいくつかを確かめるだけでは罠にはまる――パターンは40回成り立った後で41回目に崩れることもある。数学的帰納法は、有限の論証で無限に多くの場合をすべて片付ける道具だ。ドミノの列と同じ仕組みで動く：最初を倒し、倒れたものが必ず次を倒すと保証すれば、列全体が倒れる。このレッスンではその機械を組み立て、和と整除の主張に適用し、静かに証明を壊す2つの罠――1か所でも成り立たない帰納ステップと、与えられた仮定を使わない欠陥――を学ぶ。
パターンは魅力的だ。関数 f(n) = n2 − n + 41 を見てみよう。正の整数を代入してみると：41, 43, 47, 53, 61, 71, … ――どれも素数だ。続けても同じ。n = 10 でも、n = 20 でも、n = 30 でも、n = 40（このとき f(40) = 1601、素数）でも素数のまま。40回連続で成り立った。「n2 − n + 41 は常に素数」という法則は正しいのだろうか？
誤りだ。n = 41 で魔法は解ける：
f(41) = 412 − 41 + 41 = 412 = 1681 = 41 × 41，
これは明らかに素数ではない――412 と書いた瞬間に 41 という因数が見える。40回の確認はまったく意味がなかった。パターンはあくまで予想であって、決して証明ではない。有限個の例がいくら積み上がっても、無限に多くある正の整数すべてについての主張を保証することはできない。すべての n を一度に射程に収める論証が必要なのだ。
「最初のいくつかで成り立ったから正しい」は数学ではない。少数の項から規則を読み取るのは、26.1 で出てきたのと同じ誤りだ：2, 4, 8, … は必ずしも 2n−1 とは限らない。すべての正の整数について命題が成り立つことを証明するには、すべての n を網羅できる方法が必要だ――それがまさに帰納法だ。Stage 16 の背理法の兄弟分にあたり、どちらも「いくつか確かめた」の先へ踏み出す。
床の上に無限に続くドミノの列を立てる。すべて倒れると結論したい。一つ一つ押す必要はない――それでは永遠にかかる。代わりに、2つの事実を確かめればいい：
① 最初のドミノが倒れる。
② あるドミノが倒れると、必ず次のドミノを倒す。
この2つの事実だけで、論理が後をやってくれる。最初が倒れる（①による）。それが倒れたから2番目が倒れる（②による）。2番目が倒れたから3番目が倒れる（②を再び使って）。連鎖は止まらないから、どこを指差しても n 番目のドミノは必ず倒れる。これが数学的帰納法の原理を、木のドミノで表したすべてだ。
スライダーを動かして倒れる波を列に送り込もう。倒れた（緑）ドミノが立っている（スレート色）ドミノを追い越していく様子を見て、なぜすべてが倒れなければならないかを読み取ろう。
力は連鎖にある。事実②は「ドミノ5が倒れる」ではない――「もしあるドミノが倒れたら、その次も倒れる」という、すべての位置に同時に適用できる単一のルールだ。それを最初の一押しと組み合わせれば、ドミノが結論を無限の先まで無料で運んでくれる。「n = 7 で成り立つ」を個別に証明するのではなく、リンクを証明してそれを伝播させるのだ。
ドミノを証明のテンプレートに翻訳しよう。すべての正の整数 n について証明したい命題を P(n) とする。帰納法が求めるのは、ちょうど2つのことだ：
① 基底ステップ。P(1) が真であることを示す――n = 1 で命題を直接確かめる。これが「最初のドミノが倒れる」だ。
② 帰納ステップ。任意の正の整数 k に対して P(k) が真だと仮定する――この仮定が帰納法の仮定――そしてそれを使って P(k+1) が真であることを証明する。これが「倒れたドミノは必ず次を倒す」だ。
両方が完成すると、帰納法の原理によりP(n) はすべての正の整数 n に対して真と結論できる。基底ステップが導火線に火をつけ、帰納ステップがそれを永遠に燃やし続ける。
帰納ステップでは P(k) を仮定することが許されている――それが前のドミノから受け取るギフトだ。P(k+1) を仮定することは許されない；それこそが導かなければならないものだ。この操作の全体は「P(k) ⇒ P(k+1)」だ。もし仮定 P(k) を実際には一度も使っていないと気づいたら、連鎖は切れており証明は有効ではない。
実際の命題でこの機械を動かす時が来た。2ステップの方法をステップを隠さずに声に出して実行しよう。
P(n) を命題 Sn = 1 + 2 + ⋯ + n = n(n+1)2 とする。 （このガウスの公式は26.2 で出てきた；ここでは厳密に証明する。）
基底ステップ（n = 1）。左辺は 1 だけ。右辺は 1·22 = 1。 一致するので P(1) 成立 ✓。最初のドミノが倒れた。
帰納ステップ。ある k ≥ 1 について P(k)、すなわち Sk = k(k+1)2 を仮定する。P(k+1)、すなわち Sk+1 = (k+1)(k+2)2 を示さなければならない。次の部分和は古い部分和にもう1項 (k+1) を加えたものだ：
Sk+1 = Sk + (k+1) = k(k+1)2 + (k+1) = k(k+1) + 2(k+1)2 = (k+1)(k+2)2.
中間の操作で仮定を使った――Sk を k(k+1)/2 に置き換えた――そして共通因数 (k+1) を括り出した： k(k+1) + 2(k+1) = (k+1)(k + 2)。これがまさに P(k+1) だ。✓ 基底ステップと帰納ステップの両方が完成したので、公式はすべての正の整数 n に対して成り立つ。
k を調整して、ステップの両辺―― Sk + (k+1) と (k+1)(k+2)/2 ――が計算されて等しくなる（緑の ✓）のを確認しよう。部分和の点はちょうど放物線 n(n+1)/2 の上に乗っているので、図は嘘をつけない。
帰納法は和だけのものではない。P(n) を「5n − 1 は 4 で割り切れる」とする。整除の場合のコツは、因数を分離して仮定を再利用することだ。
基底ステップ（n = 1）。51 − 1 = 4 = 4 · 1、4 で割り切れる。 P(1) 成立 ✓。
帰納ステップ。ある整数 m について 5k − 1 = 4m と仮定する（これが仮定―― 5k − 1 は 4 の倍数だ）。次の場合を見て、5 の因数を1つ分離する：
5k+1 − 1 = 5 · 5k − 1 = 5(5k − 1) + 5 − 1 = 5 · 4m + 4 = 4(5m + 1).
結果は整数 (5m + 1) の 4 倍だから、5k+1 − 1 は 4 で割り切れる ――これが P(k+1) だ。✓ 仕組みをもう一度確認：新しい式が古い式（5k − 1）を含むように書き直し、仮定 4m を代入して整理した。両ステップ完成、よって 5n − 1 はすべての正の整数 n に対して 4 で割り切れる。（確認：52−1 = 24 = 4·6、53−1 = 124 = 4·31。✓）
繰り返し使う操作は「(k+1) の場合を k の場合が現れるように変形する」ことだ。5k+1−1 では 5·5k−1 = 5(5k−1) + 4 と書いた。最初の塊は仮定により 4 で割り切れる；残りの +4 はそれ自身 4 で割り切れる。4 の倍数の和 ⇒ 4 の倍数。同じテンプレートで n3 − n が 6 で割り切れること、3n − 1 が 2 で割り切れることも証明できる――前の場合が再び現れるような因数を見つけよう。
帰納法は両方の事実が確かめられたときだけ確固としている。一方を落とすと証明は崩れる――しかも間違っているように見えないこともある。初心者が陥る2つの罠がある。
有名な偽証明がある：n 頭の馬からなる任意のグループは全部同じ色だ、というものだ。基底ステップは正しい：P(1) ―― 1頭の馬のグループは自明に1色だ。手品が隠れているのは帰納ステップだ：任意の k+1 頭の馬の群れから1頭を除くと k 頭のグループ（仮定により全部同色）になり、それを戻して別の1頭を除くと（また全部同色）、2つの重なるグループが k+1 頭全体を同色にすると主張する。そこでこの論証は P(k) ⇒ P(k+1) を主張し……「すべての馬は同色」と「結論する」。
結論は馬鹿げているから何かが壊れている――壊れているのは帰納ステップであって、基底ステップではない。重なりの論証は2つの小グループが実際に馬を共有することが必要で、k ≥ 2 ではそれが成り立つ――しかしk = 1 という一つの値で失敗する：リンク P(1) ⇒ P(2) が偽なのだ。1頭から2頭に増やすとき、2つの1頭グループに共通の馬はいないから、2頭を同色にする力は何もない。連鎖の1か所に切れたリンクがあれば――基底ステップが真で他のすべてのリンクが健全でも――波は2番目のドミノに届かない。含意はすべての k で例外なく成り立たなければならない。
これは基底ステップが欠けているか偽である場合とは別の失敗様式だ。その場合は帰納ステップがすべての k で完璧でも、最初のドミノを押すものがなければ何も始まらない――連鎖は完全だが休止している。（たとえば「2n > n2」は大きな n では健全なステップを持つが、n = 2, 3, 4 で偽の基底を持つため、すべての n で真ではない。）どちらの様式も証明を壊す；欠けているリンクがどちらかを診断しよう――火花か、接続の一つか。
帰納ステップは仮定 P(k) を使わなければならない。P(k+1) の論証が P(k) に一切立ち戻らなければ――(k+1) の場合をこっそりゼロから再証明したり、P(k+1) 自身をひそかに仮定したりすれば――ドミノの間にリンクはない。一つ一つを手で押さなければならず、無限はつかめない。正しいステップには必ず古い場合を代入する行がある（我々がやったように：Sk を k(k+1)/2 で、5k−1 を 4m で置き換える）。
基底ステップなし = 証明なし：ドミノが始まらない――最初を押すものがない。1か所でも失敗するステップ = 証明なし：連鎖に切れたリンクがあるから、波がそこで止まる（「馬は同色」の誤謬―― P(1) ⇒ P(2) が偽だ）。仮定の実質的な使用なし = 証明なし：ドミノが触れ合わないから波が伝わらない。そして P(k+1) を証明するために P(k+1) を仮定してはならない――それは循環論法だ。きれいな帰納法はこう読む：基底ステップ ✓；P(k) を仮定する；そこからすべての k について P(k+1) を導く ✓；よってすべての n について P(n)。
数学的帰納法は、2つの事実――基底ステップと先に進めるリンク――を確かめることで、有限の論証ですべての正の整数について命題 P(n) を証明する。このテンプレートを手元に置いておこう：
| ステップ | すること | ドミノの絵 |
|---|---|---|
| ① 基底ステップ | P(1) を直接確かめる（真である） | 最初のドミノが倒れる |
| ② 帰納ステップ | P(k) を仮定し、P(k+1) を証明する――そして P(k) を実際に使う | 倒れたものが次を倒す |
| 結論 | P(n) はすべての正の整数 n で成り立つ | 全部倒れる |
| すること | 基底ステップを確かめる；(k+1) の場合に仮定を代入してすべての k でステップが成り立つようにする | 連鎖のリンク |
| してはいけないこと | 基底ステップを飛ばす · ステップを1か所（例：P(1)⇒P(2)）で失敗させる · P(k+1) を仮定する · P(k) を使い忘れる | ステップが壊れる ⇒ 「馬は同色」 |
基底ステップは省略できないし、帰納ステップは仮定を本当に使わなければ無意味だ。次の26.6 では、数列を実際の問題に応用する――貯蓄、複利、ローン、そしてフィボナッチの兎の話で、比が黄金比 φ ≈ 1.618 に近づいていく。
アイシャは「n2 − n + 41 は素数だ」という主張を n = 1, 2, 3 で確かめ、41, 43, 47 ――すべて素数――を見つけた。彼女はこれですべての n について主張が証明されたと宣言した。何が間違いで、主張が最初に崩れる n はどこか？
少数の場合を確かめることはすべての n についての証明にはならない――パターンは後で崩れることがある。この主張はn = 41 で最初に崩れる：f(41) = 412 − 41 + 41 = 412 = 1681 = 41 × 41、合成数だ。40回連続で素数だったことは何も証明しない。
P(n) の帰納法による証明では、2つの必須ステップは何か、そしてどちらが「最初のドミノが倒れる」に対応するか？
① 基底ステップ：P(1) が真であることを示す――これが「最初のドミノが倒れる」だ。② 帰納ステップ：P(k)（帰納法の仮定）を仮定して P(k+1) を証明する――これが「倒れたドミノが次を倒す」だ。両方が必要で、合わせてすべての正の整数 n について P(n) が得られる。
1 + 2 + ⋯ + n = n(n+1)2 の帰納ステップを完成させよ：Sk = k(k+1)/2 を仮定して、Sk+1 = (k+1)(k+2)/2 を示せ。
Sk+1 = Sk + (k+1) = k(k+1)/2 + (k+1) = [k(k+1) + 2(k+1)]/2 = (k+1)(k+2)/2 ✓。仮定を使って Sk を置き換え、(k+1) を括り出した。これがまさに P(k+1) だ。
帰納法を使って、すべての正の整数 n に対して 5n − 1 は 4 で割り切れることを証明せよ。
基底：51 − 1 = 4 = 4·1 ✓。ステップ：ある整数 m について 5k − 1 = 4m と仮定する。すると 5k+1 − 1 = 5·5k − 1 = 5(5k − 1) + 4 = 5·4m + 4 = 4(5m + 1)、4 の倍数だ ✓。よって主張はすべての n で成り立つ。
「すべての馬は同じ色」の論証は、正しそうに見える帰納ステップを持つが結論は偽だ。基底ステップ P(1) は実際に正しい――では証明のどの部分が失敗していて、それはなぜか？
基底ステップは正しい（1頭の馬のグループは1色だ）；失敗しているのは帰納ステップ――しかも1か所だけだ。リンク P(1) ⇒ P(2) が偽だ：重なりの論証は2つの小グループが馬を共有することが必要だが、k = 1 から k = 2 に移ると共通の馬はいない（1頭ずつ、交互に取り除く）。含意は k ≥ 2 では成り立つが k = 1 で壊れるから、連鎖に切れたリンクがあり波は2番目のドミノに届かない。1か所でも失敗するステップは、基底ステップが真であっても、何も証明しない。
帰納ステップで、ある生徒が「P(k+1) が真だと仮定する……したがって P(k+1) は真だ」と書いた。帰納法のどのルールが破られていて、代わりに何を仮定すべきだったか？
証明すべきこと自体を仮定している――これは循環論法だ。仮定してよい帰納法の仮定は P(k)（前の場合）であり、そこから P(k+1) を導かなければならない。P(k+1) を仮定するとドミノ間のリンクを飛ばすことになり、何も証明されない。
6問で理解を定着させよう。正しいと思う答えをタップしてね。
このレッスンは数学的実践の基準 MP3（妥当な論証を構成し、他者の推論を批判的に評価する）を育む。生徒は経験的なパターン発見が予想であって証明ではないことを理解し、帰納法の2部構成の演繹テンプレートを学ぶ。HSA-SSE.A.2 と HSA-SSE.B.4（式の変形と数列についての推論）の代数的流暢さを構築し、等差数列の和 1 + 2 + ⋯ + n = n(n+1)/2 を単に主張するのではなく証明する。また HSF-BF.A.1/A.2 との接続として、部分和数列 Sn を n の関数として扱う。n2−n+41 の罠は場合の確認が証明にならない理由を明確にし、「馬は同色」の反例は帰納ステップがすべての k で成り立たなければならないことを示す――1か所の切れたリンク（ここでは P(1) ⇒ P(2)）は、基底ステップが真であっても論証を無効にする。