数学的帰納法
“帰納法とは、たった2つの確認で無限個のドミノを倒す技。”
数式
[ P(1) ∧ ( P(k) ⟹ P(k+1) ) ] ⟹ ∀n ≥ 1, P(n)読み方: 最初の場合が真であり、ある場合が真であれば次も必ず真になるなら、その命題はすべての自然数について真である
- P(n)
- — 自然数nについて証明したい命題
- P(1)
- — 基礎——最初のドミノを倒す
- P(k) ⟹ P(k+1)
- — 帰納段階——それぞれのドミノが次のドミノを倒す
- ∀n ≥ 1
- — したがってすべての自然数について成り立つ
きっかけ
無限個の場合をたった2行で証明する——最初のドミノを倒し、どのドミノも次を倒すことを示せばそれで終わりです。
やさしく言うと
数学的帰納法は「すべての自然数nについて」命題が真であることを証明します。(1) n=1で成り立つこと（基礎）を示し、(2) n=kで成り立てばn=k+1でも成り立つこと（帰納段階）を示す——ドミノのように、すべてが倒れていきます。
直感
果てしなく続くドミノの列を思い浮かべてください。1つずつ手で倒すことはできません。しかし確かめることはたった2つだけです——最初の1つが倒れること、そして「どのドミノが倒れても、その隣が倒れる」こと。すると1番目が2番目を、2番目が3番目を…と永遠に倒し続け、すべてが倒れます。有限の確認2つで無限を制覇するのです。
どう作られるか
2つの部分からなります——基礎と帰納段階です。基礎は出発点（通常n=1）が成り立つことを直接確かめます。帰納段階は「P(k)が真である」という帰納法の仮定を使ってP(k+1)を導きます。どちらも必要です——最初のドミノがなければ何も倒れず、連鎖がなければ1つしか倒れません。
例
1+2+⋯+n = n(n+1)/2を証明します。基礎n=1：左辺は1 = 1·2/2 = 1 ✓。帰納段階：1+⋯+k = k(k+1)/2と仮定すると、1+⋯+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2となり、n=k+1のときの式と一致 ✓。よってすべてのnで成り立ちます。
よくある誤解
「P(k)が真であると仮定する」という帰納法の仮定は、証明したいことを最初から仮定しているように見えて循環論法に思えますが、そうではありません。P(k)が実際に真だと主張しているのではなく、「それが真なら次も真」という条件付きのつながり（ドミノとドミノの間の隙間）だけを証明しているのです。
どこで使うか
和や不等式の公式の証明、アルゴリズムの正しさの検証（再帰やループ）、データ構造やコンパイラの正しさの証明、数論や組合せ論の数え切れない定理——数学と計算機科学で無限個の場合が現れるあらゆる場所に使われます。
どこから来たか
パスカルは1600年代、パスカルの三角形を扱う中で明示的にこれを用い、1800年代にはペアノが自然数の公理の中に組み込み、論理学の柱の一つとしました。
前提概念
確認問題
数学的帰納法で、基礎に加えて証明すべきことは何ですか？
- P(k)が真ならP(k+1)も真であること✓
- ある大きなnについてP(n)が真であること
- P(n)が決して偽にならないこと
- それ以上は何も必要ない
練習
公式1+2+⋯+n = n(n+1)/2を使って1+2+⋯+10を計算しなさい。
答え: 55
- n=10を代入：10·11/2
- = 110/2 = 55
ポイント: 帰納法で公式を証明してしまえば、あとは代入するだけ。
1+2+⋯+100を計算しなさい。
答え: 5050
- 100·101/2
- = 10100/2 = 5050
ポイント: 少年ガウスが数秒で解いたと伝えられる、まさにその和。
最初のn個の奇数の和1+3+5+⋯+(2n−1) = n²について、n=5のときの値を求めなさい。
答え: 25
- 1+3+5+7+9 = 25
- = 5² = 25
ポイント: 奇数の和は平方数になる——帰納法の定番の例。
1+2+⋯+n = n(n+1)/2を帰納法で証明しなさい（基礎と帰納段階を書くこと）。
答え: undefined
- 基礎n=1：1 = 1·2/2 = 1 ✓
- 仮定：1+⋯+k = k(k+1)/2
- (k+1)を加える：k(k+1)/2 + (k+1) = (k+1)(k+2)/2、これはn=k+1のときの公式 ✓
ポイント: 基礎＋帰納段階＝無限個の場合に対する完全な証明。