数学的帰納法ってなに？2 つの確認で無限個の命題が示せる

$1 + 2 + 3 + \dots + n = \frac{n ( n + 1 )}{2}$ は、 $n = 1$ でも $n = 100$ でも成り立ちます。ところが自然数は無限にあるので、1 つずつ入れて確かめる方法では終わらない。

数学的帰納法は、この無限を 2 つの確認に置きかえます。

n = 1

のとき成り立つことを示す。

n = k

のとき成り立つと仮定して、

n = k + 1

でも成り立つことを示す。

1 つ目を出発点、2 つ目を帰納の段階といいます。この 2 つがそろえば、すべての自然数について成り立つと言い切れる。

ドミノが端まで倒れる

最初の 1 枚を倒す。どの 1 枚が倒れても次の 1 枚が倒れるようにしておく。並べたドミノは、この 2 つで端まで倒れる。

命題を $P (n)$ と書きます。 $P (1)$ が正しく、 $P (1)$ から $P (2)$ が導けるので $P (2)$ も正しい。同じ理屈で $P (3)$ 、 $P (4)$ と続く。

どの番号 $N$ を持ってきても、 $1$ から $N$ まで有限回たどれば届く。無限個の命題を 2 つの確認で押さえられるのは、この「有限回でたどり着ける」が効いているからです。

答案の骨組み

書き方はほぼ決まっています。

n = 1 のとき、左辺と右辺を計算して一致を示す

n = k のとき成り立つと仮定する

仮定を使って n = k+1 のときを示す

よってすべての自然数 n で成り立つ

点数が動くのは 3 番目です。仮定した式をどこで使ったのかが読みとれるように書く。仮定を使わずに示せてしまうなら、そもそも帰納法はいりません。

例：和の公式

$1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ を証明します。

$n = 1$ のとき、左辺は $1$ 、右辺は $\frac{1 \cdot 2}{2} = 1$ で一致。

$n = k$ で成り立つと仮定します。つまり $1 + 2 + \dots + k = \frac{k ( k + 1 )}{2}$ が使える。

$n = k + 1$ のときの左辺は、最初の $k$ 項ぶんに仮定をあてて書きかえられます。

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

あとは共通の $(k + 1)$ でくくる。

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

これは公式の $n$ に $k + 1$ を入れた形。よってすべての自然数で成り立ちます。

例：平方の和

$1^{2} + 2^{2} + \dots + n^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$ を証明する。

$n = 1$ のとき、左辺は $1$ 、右辺は $\frac{1 \cdot 2 \cdot 3}{6} = 1$ 。

$n = k$ を仮定して $n = k + 1$ を調べる。

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

中かっこの中は $2 k^{2} + 7 k + 6$ で、 $(k + 2) (2 k + 3)$ と因数分解できる。

$\frac{( k + 1 ) ( k + 2 ) ( 2 k + 3 )}{6}$

右辺の $n$ に $k + 1$ を入れた形と、そのまま重なりました。 $(k + 1)$ でくくってから中を整理する、という順番を守ると計算が短くなる。

例：出発点が 1 でない場合

$n \geq 5$ のとき $2^{n} > n^{2}$ を証明します。

$n = 4$ では $16 = 16$ で不等号が成り立ちません。出発点は $n = 5$ 。

$n = 5$ のときは $2^{5} = 32$ 、 $5^{2} = 25$ で $32 > 25$ 。

$n = k (k \geq 5)$ で $2^{k} > k^{2}$ を仮定して、両辺を $2$ 倍する。

$2^{k + 1} = 2 \cdot 2^{k} > 2 k^{2}$

あとは $2 k^{2} \geq (k + 1)^{2}$ を示せば足ります。差をとると $k^{2} - 2 k - 1 = (k - 1)^{2} - 2$ で、 $k \geq 5$ なら $(k - 1)^{2} \geq 16$ だから正。

$2^{k + 1} > 2 k^{2} \geq (k + 1)^{2}$

出発点は $1$ とはかぎりません。命題が成り立ちはじめる番号を土台にする。

出発点を書き忘れるとどうなるか

$P (n)$ を「 $n = n + 1$ 」という誤った命題にしてみます。 $P (k)$ を仮定して両辺に $1$ を足すと $k + 1 = k + 2$ となり、 $P (k + 1)$ が導けてしまう。

帰納の段階は通っているのに、結論はでたらめです。 $P (1)$ が成り立たないため、どのドミノも最初から倒れていません。

出発点の確認は形式ではなく、証明の土台そのものです。ここが抜けた答案は、何も示していないことになる。

前の 1 つでは足りないとき

$a_{n + 2} = a_{n + 1} + a_{n}$ のように 2 つ前までさかのぼる数列では、 $n = k$ の仮定だけでは $n = k + 1$ を示せません。仮定を 2 つ置きます。

仮定を 1 つ置く形

直前の $n = k$ だけを仮定して $n = k + 1$ を示す。次の項が 1 つ前だけで決まるとき

仮定を 2 つ置く形

$n = k$ と $n = k + 1$ を仮定して $n = k + 2$ を示す。2 つ前までさかのぼるとき

仮定を 2 つ置く形では、出発点も 2 つ確かめる。 $n = 1$ と $n = 2$ の両方を示しておかないと、 $n = 3$ へつなげられない。

必要な情報が直前だけで足りるかどうかで、どちらの形にするかが決まります。

数学的帰納法で、出発点の確認を書き忘れるとどうなりますか。

証明は成り立つが減点される
帰納の段階が正しくても、結論は保証されない
出発点は $n = 1$ に限るので書かなくてよい
仮定を 2 つ置く形にすれば不要になる

__RESULT__

最初のドミノが倒れなければ、何枚並べても倒れません。 $n = n + 1$ という誤った命題でも、帰納の段階だけは通ってしまいます。

$n \geq 3$ で成り立つ命題を帰納法で示すとき、出発点で確かめるのはどれですか。

$n = 1$ のとき
$n = 2$ のとき
$n = 3$ のとき
$n = 4$ のとき

__RESULT__

命題が成り立ちはじめる番号を土台にします。 $n = 3$ を示し、 $k \geq 3$ で $P (k) \Rightarrow P (k + 1)$ を示せば、 $3$ 以上のすべてで成り立ちます。

出発点と帰納の段階、確かめるのはこの 2 つです。どちらか一方だけでは、無限に並んだ命題のどこにも届きません。

自然数は無限にあるので、$1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ に $n$ を 1 つずつ入れて確かめる方法では終わりません。最初の 1 枚を倒すことと、どの 1 枚も次を倒すこと。この 2 つでドミノは端まで倒れます。答案の骨組みが 4 行で決まっていること、点数が動くのは仮定をどこで使ったかを書く場所であること、和の公式と平方の和と $2^n > n^2$ の運び方を順に見ていく。出発点を書き忘れると $n = n+1$ まで証明できてしまう。