数学的帰納法 — ドミノの論法

無限個の主張を、2手で

「すべての自然数nについて 1 ＋ 2 ＋ … ＋ n ＝ n(n ＋ 1)/2」——n ＝ 1、2、3、…と無限にある主張を、ぜんぶ確かめることはできない。

そこでドミノ倒しを思い浮かべよう。無限に並んだドミノをすべて倒すには、2つのことを確認すれば足りる。

1. 最初の1枚が倒れる
2. どの1枚についても、それが倒れたら次の1枚も倒れる

この2つがそろえば、1枚目 → 2枚目 → 3枚目 → …と、すべてが倒れる。これを証明の形式にしたのが数学的帰納法だ：

• ［1］ n ＝ 1 のとき成り立つことを示す
• ［2］ n ＝ k のとき成り立つと仮定して、n ＝ k ＋ 1 のときも成り立つことを示す

借りを返す — 和の公式の証明

例1 ：1 ＋ 2 ＋ … ＋ n ＝ n(n ＋ 1)/2 を証明しよう。

［1］ n ＝ 1：左辺 ＝ 1、右辺 ＝ 1 × 2/2 ＝ 1。成立 ✓

［2］ n ＝ k で成立すると仮定する：1 ＋ 2 ＋ … ＋ k ＝ k(k ＋ 1)/2。

このとき n ＝ k ＋ 1 の左辺は——

\[\underbrace{1 + 2 + \cdots + k}_{仮定がつかえる！} + (k + 1) = \frac{k(k+1)}{2} + (k+1)\]

(k ＋ 1) でくくると（因数分解！）——

\[= (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}\]

これは公式の n に k ＋ 1 を入れた形そのもの。つまり n ＝ k ＋ 1 でも成立 ✓

［1］［2］より、すべての自然数nで成立する。∎

ガウスの「逆順にたす」（A3の最初）とはまったく別の道で、同じ公式にたどり着いた。発見の方法（ガウス）と証明の方法（帰納法）——両方持っていることが数学の強さだ。

例2 ：「2ⁿ ＞ n がすべての自然数で成り立つ」も同じ型で証明できる。［1］ 2¹ ＝ 2 ＞ 1 ✓。［2］ 2ᵏ ＞ k と仮定すると 2ᵏ⁺¹ ＝ 2 × 2ᵏ ＞ 2k ≧ k ＋ 1（k ≧ 1 だから）✓。

仮定するのは「ずるく」ない

［2］で「n ＝ k で成り立つと仮定」と聞くと、証明したいことを先に使う循環論法に見えるかもしれない。でもちがう——［2］が示すのは「もしk枚目が倒れるなら、k＋1枚目も倒れる」という条件つきの主張（S2の「ならば」！）だけ。実際に倒すのは［1］の最初の1枚。2つが組み合わさって、はじめて全部が倒れる。

よくあるまちがい

その1：［1］を省略する。 「倒れたら次も倒れる」だけでは、1枚も倒れていないかもしれない。実際、「n ＋ 1 ＝ n ＋ 2」のような偽の主張でも［2］型の推論は書けてしまう（両辺に1をたすだけ）。［1］がないと帰納法は無効だ。

その2：［2］で仮定を使わない。 仮定 k(k ＋ 1)/2 を使わずに直接計算しようとして行き詰まるパターン。帰納法のうまみは「前の段の結果を使ってよい」こと——左辺の中に「k までの和」の形を見つけて置き換えるのが定石。

れんしゅう

もっと れんしゅう

ボタンを おすと、あたらしい もんだいが でて くるよ。なんかいでも れんしゅう できるよ。

あたらしい もんだいを つくる