数学的帰納法

数学的帰納法は、ある n₀ 以上のすべての整数 n について命題 P(n) を証明するものであり、二つの部分から成ります。直接確認される出発点 P(n₀) と、k ≥ n₀ となるすべての k において P(k) ならば必ず P(k + 1) になるという論証である帰納部のステップです。倒れるドミノが次々と隣を押し倒していくように、これら二つが合わさることで初めてすべての n に到達します。

各記号の意味

P(n)

n についての命題。それぞれの n において単に真か偽かのどちらかとなります。

n₀

出発点。証明が始まる場所であり、手作業で確認します。

k

ステップ内での一般的な n。論証は P(k) を仮定し、P(k + 1) に到達しなければなりません。

公式の導き方

1. なぜこれら二つの部分で十分なのか。 出発点が真であり、k ≥ n₀ のすべての k でステップが成立するとします。しかし n₀ 以降のどこかで P が偽になると仮定しましょう。偽となる n の中には最小のものが存在します。それを m と呼びます。P(n₀) は確認済みであるため m は n₀ ではなく、したがって m − 1 ≥ n₀ となります。m が偽となる最小の値であったため、P(m − 1) は真です。するとステップによって P(m) が導かれますが、これは P(m) が偽であるという仮定と矛盾します。ゆえに、偽となる場所は存在しません。ここでは両方の部分が使われています。出発点がなければ m が n₀ になる可能性があり、たった一つの k でステップが欠けていれば m が k + 1 になる可能性があるからです。
2. なぜ n² + n + 41 は破綻しなければならなかったのか。 n = 40 のとき、最初の二つの項がまとまって 40² + 40 = 40 × 41 となるため、40² + 40 + 41 = 40 × 41 + 41 = 41 × 41 となります。n = 41 ではすべての項が 41 の倍数となり、その値は 41 × 43 です。この考えはさらに一般化できます。定数ではない整数係数の多項式が素数のみを生成し続けることはありません。最初にどれほど多くの素数を生成したとしてもです（Lehman, Leighton, Meyer が問題 1.25 でこれを証明しています）。そのため、この命題に対する帰納部のステップは最初から存在し得なかったのです。
3. n ≥ 5 のすべての n に対する 2ⁿ > n²（正しい証明）。 出発点：2⁵ = 32 > 25 = 5²。ステップ：k ≥ 5 とし、2ᵏ > k² を仮定します。すると 2ᵏ⁺¹ = 2 · 2ᵏ > 2k² = k² + k² となります。k ≥ 5 なので k² ≥ 5k = 2k + 3k > 2k + 1 であり、したがって 2k² > k² + 2k + 1 = (k + 1)² となって、2ᵏ⁺¹ > (k + 1)²、すなわち P(k + 1) が導かれます。ステップ自体は k ≥ 3 であれば成立します。P(2)、P(3)、P(4) が偽であるため、出発点はどうしても 5 でなければならなかったのです。