数学的帰納法——ドミノ倒しで無限を証明する

なぜ「無限個」の命題を証明できるのか

「1 から 100 まで全部の整数について何かが成り立つ」ことを証明するなら、100 個確認すれば済みます。では「すべての自然数 $n$ について $P(n)$ が成り立つ」——つまり「無限個の命題が全部成り立つ」ことを、どうやって証明できるのでしょうか？ $n$ は無限にあります。全部確認するのは不可能です。

そこで数学的帰納法という戦略を使います。

ドミノ倒しのアナロジー——「最初のドミノが倒れる」「あるドミノが倒れたら必ず次のドミノも倒れる」、この 2 つが保証されれば、論理的に全部のドミノが倒れます。100 個でも 100 万個でも、原理は同じです：

1. 最初のドミノが倒れる（基底ステップ：$P(1)$ が成立）
2. あるドミノが倒れたら次も倒れる（帰納ステップ：$P(k)$ が成立 $\Rightarrow$ $P(k+1)$ が成立）

この2つが確認できれば、論理的にすべての $n$ について $P(n)$ が成立します。

数学的帰納法の構造

① 基底ステップ: P(1) を証明する
② 帰納ステップ: 「P(k) が成立する」と仮定して P(k+1) を証明する
③ 結論: すべての自然数 n について P(n) が成立する

帰納仮定（induction hypothesis）：帰納ステップで「$P(k)$ が成立する」と仮定する部分——「$k$ 番目のドミノが倒れたと仮定して、$k+1$ 番目も倒れることを示す」。

ドミノ倒しアニメーション

var t, dominoCount, i, fallen, phase;

t = 0;
dominoCount = 12;

function loop() {
ctx.clearRect(0, 0, W, H);
t += 0.018;

var domW = 18, domH = 50, gap = (W - 60) / dominoCount;
var baseY = 220;

fallen = Math.min(dominoCount, Math.floor(t * 2.5));

for (i = 0; i < dominoCount; i++) {
  var cx = 40 + i * gap;
  var isFallen = i < fallen;
  var isFalling = i === fallen && (t * 2.5 - fallen) < 1;
  var angle = 0;
  if (isFalling) { angle = (t * 2.5 - fallen) * Math.PI / 2; }
  if (isFallen) { angle = Math.PI / 2; }

  var hue = isFallen ? '#22c55e' : (isFalling ? '#fbbf24' : '#60a5fa');
  ctx.fillStyle = hue;

  ctx.save();
  ctx.translate(cx, baseY);
  ctx.rotate(angle);
  ctx.fillRect(-domW/2, -domH, domW, domH);
  ctx.strokeStyle = '#0d1117';
  ctx.lineWidth = 1;
  ctx.strokeRect(-domW/2, -domH, domW, domH);

  // label
  ctx.fillStyle = '#fff';
  ctx.font = 'bold 10px sans-serif';
  ctx.textAlign = 'center';
  if (!isFallen || angle < Math.PI / 4) {
    ctx.fillText('n='+(i+1), 0, -domH/2);
  }
  ctx.restore();
}

// annotations
ctx.fillStyle = '#60a5fa';
ctx.font = '13px sans-serif';
ctx.textAlign = 'center';
ctx.fillText('① P(1): 基底ステップ', 40 + 0 * gap, 250);
ctx.fillStyle = '#fbbf24';
ctx.fillText('② P(k)⇒P(k+1): 帰納ステップ', W/2, 270);
ctx.fillStyle = '#22c55e';
ctx.fillText('✓ すべての n で成立', W - 80, 250);

if (t > dominoCount / 2.5 + 1) t = 0;

requestAnimationFrame(loop);
}
loop();

証明例1：$\sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}$

「1 から $n$ まで全部の整数を足したら $n(n+1)/2$ になる」——ガウスが小学生のときに瞬時に計算したという有名な公式です。

命題 $P(n)$：$1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$

① 基底ステップ（$n = 1$）

左辺 $= 1$、右辺 $= \dfrac{1 \times 2}{2} = 1$。等しい。✓——「ドミノの最初の 1 個が倒れた」

② 帰納ステップ

「$k$ 番目のドミノが倒れたと仮定して、$k+1$ 番目も倒れることを示す」——$P(k)$ が成立、すなわち $1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}$ を仮定する。

$P(k+1)$ を証明：$1 + 2 + \cdots + k + (k+1)$

$= \frac{k(k+1)}{2} + (k+1) \quad (\text{帰納仮定を使用})$

$= (k+1)\left(\frac{k}{2} + 1\right) = (k+1) \cdot \frac{k+2}{2} = \frac{(k+1)(k+2)}{2}$

これは $P(k+1)$ の形 $\dfrac{(k+1)((k+1)+1)}{2}$ と一致。✓——「$k$ 番目が倒れたら $k+1$ 番目も倒れる」

結論：すべての自然数 $n$ について命題が成立する。$\blacksquare$

証明例2：$2^n > n$（指数の優位性）

「どれだけ大きな $n$ でも、$2^n$ は必ず $n$ より大きい」——これを全部の自然数について証明します。

命題 $P(n)$：$2^n > n$

① 基底ステップ（$n = 1$）

$2^1 = 2 > 1$ ✓

② 帰納ステップ

$P(k)$：$2^k > k$ を仮定する。

$2^{k+1} = 2 \cdot 2^k > 2k = k + k \ge k + 1 \quad (k \ge 1 \text{ のとき } k \ge 1)$

よって $2^{k+1} > k+1$、$P(k+1)$ が成立。✓——「$2^k > k$ が成り立つなら、$2^{k+1} = 2 \times 2^k > 2k \geq k+1$ も成り立つ」

よくある間違い

間違い1：基底ステップを忘れる

帰納ステップだけでは不十分です——「$P(k) \Rightarrow P(k+1)$」が成り立っても、スタートが確認されていなければどのドミノも倒れません。「1枚目が倒れていなければ、連鎖は起きない」。

間違い2：帰納仮定を正しく使わない

帰納ステップで $P(k+1)$ を証明するとき、$P(k)$ だけでなく、場合によっては $P(1), P(2), \ldots, P(k)$ 全部を仮定してよい場合があります（強い帰納法）。

間違い3：「全称命題」と「存在命題」の混同

帰納法は「すべての $n$ について〜」という全称命題の証明に使います——「どれか 1 つについて」の証明には使えません。

強い帰納法（完全帰納法）

「直前の 1 個だけでなく、それまでに倒れた全部を使って次が倒れることを示す」——通常の帰納法が「$P(k) \Rightarrow P(k+1)$」なのに対し、強い帰納法は「$P(1), P(2), \ldots, P(k)$ がすべて成立 $\Rightarrow P(k+1)$ が成立」という形を使います。

フィボナッチ数列の性質やゲームの理論で威力を発揮します——「前の全部の情報を使わないと次を証明できない場合に使う」。

まとめ

• 数学的帰納法は「無限個の命題」を有限のステップで証明する手法——「ドミノ倒しの原理」
• 構造：①基底ステップ（スタートを確認）+ ②帰納ステップ（連鎖を確認）
• イメージ：最初が倒れ、前が倒れれば次も倒れる——「2 つのルールだけで無限が証明できる」
• 帰納ステップでは 帰納仮定（$P(k)$ の成立）を必ず明示して使う
• 強い帰納法：$P(1) \sim P(k)$ 全部を仮定できる形——「前の全情報を使う」

次回は約数と倍数——整数の構造の基礎を学びます。