数学的帰納法の枠組み

方針

解答

⓪ 発想 — どう考え始めるか。 証明すべきは「すべての自然数 $n$ で成り立つ」こと。

自然数は無限にある。 $1$ つずつ確かめていては、永久に終わらない。

そこで、$2$ 段構えの仕掛けを使う。

• (I) $n=1$ で成り立つことを、実際に確かめる
• (II) 「$n=k$ で成り立つ」を仮定して、「$n=k+1$ でも成り立つ」を導く

この $2$ つで、なぜ無限個が片づくのか。

ドミノ倒しを思い浮かべよう。

(I) は「$1$ 枚目を倒す」こと。(II) は「$k$ 枚目が倒れれば $k+1$ 枚目も倒れる」という仕組みを作ること。

仕組みができていれば、$1$ 枚目を倒すだけで、あとは勝手に全部倒れる。

$$1\to 2\to 3\to 4\to \cdots$$

「$2$ 段で、無限個を証明する。」 この論法の枠組みそのものを、まず掴んでほしい。

(I) $n=1$ のとき。 左辺 $=1$、右辺 $=\frac{1\cdot 2}{2}=1$。成り立つ。

(II) $n=k$ を仮定する。 $1+2+\cdots +k=\frac{k(k+1)}{2}$ が成り立つとする。

この両辺に、次の項 $k+1$ を足す。

$$1+2+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1)$$

右辺を $(k+1)$ でくくって整理する。

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

これは、もとの式で $n=k+1$ とした右辺 $\frac{(k+1)\{(k+1)+1\}}{2}$ に一致する。よって $n=k+1$ でも成り立つ。

結論。 (I)(II) より、すべての自然数 $n$ で成り立つ。

まとめ:数学的帰納法は「ドミノ倒し」。(I) 最初の $1$ 枚を倒し、(II) $k$ 枚目が倒れれば $k+1$ 枚目も倒れる、を示す。この $2$ つで全部倒れる(全部で成立)。仮定した式を使うところがヤマだ。

発展 — 一歩先へ。 「たくさん確かめたから正しい」— この推論は、数学では通らない。

その理由を、痛烈に教えてくれる例がある。

オイラーの式。

$$f(n)=n^2+n+41$$

$n=0$ から順に、値を出してみよう。

$$41,43,47,53,61,71,83,97,113,131,\dots$$

すべて素数だ。

$n=20$ でも $461$($=$ 素数)。$n=30$ でも $971$($=$ 素数)。$n=39$ でも $1601$($=$ 素数)。

$n=0$ から $n=39$ まで、$40$ 個すべてが素数になる。

「これは、すべての $n$ で素数だ」と言いたくなる。

だが、$n=40$ で

$$40^2+40+41=1681=41\times 41$$

素数ではない。

$40$ 個の成功のあとに、あっさり反例が現れた。

これが「実験は証明ではない」ということだ。

もっと極端な例もある。 ある予想は、$10^{40}$ 以下のすべての数で成り立つのに、それより大きいところで破れることが証明されている(スキューズ数の話)。人類が確かめられる範囲では、永遠に反例が見つからない。

だからこそ、帰納法が要る。

帰納法の (II) は「$k$ で成り立てば $k+1$ でも成り立つ」という仕組みを証明する。仕組みさえ作れば、確かめていない先の無限個まで、まとめて保証できる。

$$\text{有限の確認}\ne \text{無限の証明}$$

「$1$ 万回試して大丈夫だった」は、数学では何も言っていないのと同じ。

逆に、$2$ 行の帰納法は、無限個を完全に押さえる。

これが、数学が「証明」にこだわる理由である。 実験は道を照らすが、道が無限に続くことを保証できるのは、証明だけなのだ。

別解

帰納法の (II) は、実は「階差の確認」にすぎない。

この見方を知ると、帰納法の計算が一気に軽くなる。

証明したい式の右辺を、関数と見る。

$$f(n)=\frac{n(n+1)}{2}$$

主張は「左辺の和 $=$ $f(n)$」だ。

(II) で何をしているか、よく見てほしい。

$n=k$ で正しいと仮定すると、左辺の和は $f(k)$。そこに新しい項 $k+1$ を足したものが、$f(k+1)$ になってほしい。

$$f(k)+(k+1)\stackrel{?}{=}f(k+1)$$

移項すれば、確かめるべきことはこれだけだ。

$$\boxed{f(k+1)-f(k)=k+1}$$

「右辺の階差が、足す項に一致するか」 — これが (II) の中身のすべてである。

実際に計算する。

$$f(k+1)-f(k)=\frac{(k+1)(k+2)}{2}-\frac{k(k+1)}{2}$$

共通因数 $\frac{k+1}{2}$ でくくる。

$$=\frac{k+1}{2}\{(k+2)-k\}=\frac{k+1}{2}\times 2=k+1✓$$

足す項 $k+1$ に、ぴったり一致した。

あとは (I) の $f(1)=1$ を確かめれば終わり。

この見方の強み。

• やることが $1$ 行に決まる。 「$f(k+1)-f(k)$ を計算して、足す項と比べる」だけ
• 式が複雑でも迷わない。 $\Sigma k^2=\frac{n(n+1)(2n+1)}{6}$ でも、やることは同じ($f$ の階差が $(k+1{)}^2$ になるか)
• なぜ帰納法が効くのかが見える。 「初項が合っていて、階差も合っている $\Rightarrow$ 全部合っている」— 階差型の漸化式そのものだ

そして、大事な但し書き。

帰納法は「確認」の道具であって、「発見」の道具ではない。 $\frac{n(n+1)}{2}$ という式は、帰納法からは出てこない。

式は、実験や工夫(逆順に足す、図で数える)から予想する。 帰納法は、その予想を確定させる最後の一手なのだ。

予想する道具と、確定させる道具。 $2$ つを両手に持って初めて、数学は進む。