数学的帰納法の使い方｜倍数の証明、一般項の予想、場合の数まで

$n^3-n$ に $n=1$ から順に入れると $0,6,24,60,120,210$ と並び、どれも $6$ で割り切れます。ただし、いくつ調べても確認であって証明にはならない。

$n$ から $n+1$ へ進んでも性質が保たれる、と示すのが数学的帰納法の役目です。使い道は和の公式にかぎらず、倍数、漸化式で定まる数列、数え上げにも広がる。

型 1：倍数であることの証明

$n^3-n$ がいつでも $6$ の倍数になることを示します。

$n=1$ のとき $1-1=0$ で、$0$ は $6$ の倍数。

$n=k$ で $k^3-k$ が $6$ の倍数だと仮定し、$n=k+1$ を計算する。

$$\begin{array}{rl}(k+1{)}^3-(k+1)& =k^3+3k^2+3k+1-k-1\\ & =(k^3-k)+3k(k+1)\end{array}$$

仮定した $k^3-k$ がそのまま第 1 項に現れました。第 2 項の $k(k+1)$ は連続する 2 整数の積なので偶数で、$3$ をかけると $6$ の倍数になる。

$6$ の倍数どうしの和なので、$n=k+1$ でも成り立ちます。仮定したかたまりと、それ以外に分ける。倍数の証明はこの一手で片づくことがほとんどです。

例：6 の n 乗引く 1

$6^n-1$ が $5$ の倍数であることを確かめます。

$n=1$ のとき $6-1=5$。

$n=k$ で $6^k-1$ が $5$ の倍数と仮定する。$6^k-1$ を作り出すために、$6$ をかけたぶんを定数で調整する。

$$6^{k+1}-1=6\cdot 6^k-1=6(6^k-1)+5$$

第 1 項は仮定から $5$ の倍数、第 2 項は $5$ そのもの。$6$ を $6^k$ の前に出し、余った定数を切り離す変形は、指数の入った倍数の問題でくり返し使えます。

型 2：一般項を予想して確かめる

漸化式で定まる数列は、いくつか計算して一般項を予想し、その予想を帰納法で確かめる、という順でも解けます。

予想までは実験でよく、最後の一段が帰納法の仕事です。

例：予想を確かめる

$a_1=2$、$a_{n+1}=2a_n-1$ の一般項を求める。

順に計算すると $a_1=2$、$a_2=3$、$a_3=5$、$a_4=9$、$a_5=17$。

$1$ ずつ引くと $1,2,4,8,16$ で $2$ のべき乗になるため、$a_n=2^{n-1}+1$ と予想します。

$n=1$ のとき $2^0+1=2$ で、$a_1$ と一致。

$n=k$ で $a_k=2^{k-1}+1$ を仮定し、漸化式に入れる。

$$a_{k+1}=2a_k-1=2(2^{k-1}+1)-1=2^k+1$$

これは $n=k+1$ を入れた形。予想が正しいと確かめられました。

例：分数の形を確かめる

$a_1=1$、$a_{n+1}=3a_n+1$ について、$a_n=\frac{3^n-1}{2}$ を証明します。

$n=1$ のとき $\frac{3-1}{2}=1$ で一致。

$n=k$ を仮定して計算する。

$$\begin{array}{rl}{a}_{k+1}& =3\cdot \frac{3^k-1}{2}+1\\ & =\frac{3^{k+1}-3+2}{2}\\ & =\frac{3^{k+1}-1}{2}\end{array}$$

分数のまま通分して進める。$3$ をかけてから $1$ を足すので、分子に $-3+2$ の計算が現れる。

型 3：数え上げ

個数を数える問題にも帰納法が使える。要素が $n$ 個ある集合の部分集合が $2^n$ 個であることを示します。

$n=1$ のとき、部分集合は空集合とその集合自身の $2$ 個。$2^1=2$ で一致します。

$n=k$ で $2^k$ 個だと仮定し、要素を 1 つ増やす。新しい要素を含まない部分集合が $2^k$ 個、含む部分集合も $2^k$ 個。

$$2^k+2^k=2^{k+1}$$

新しい要素を入れるか入れないかで 2 通りに分かれ、個数がちょうど倍になります。この分かれ方が帰納の段階そのもの。

2 つ前まで使うとき

直前の 1 つだけでは足りない場面もあります。$F_1=F_2=1$、$F_{n+2}=F_{n+1}+F_n$ で定まる数列について、$F_n<2^n$ を示す場合です。

$F_{k+2}$ を評価するのに $F_{k+1}$ と $F_k$ の両方を使うため、仮定を 2 つ置きます。出発点も $F_1=1<2$ と $F_2=1<4$ の 2 つ。

$$F_{k+2}=F_{k+1}+F_k<2^{k+1}+2^k<2^{k+1}+2^{k+1}=2^{k+2}$$

2 つ前までさかのぼる数列では、出発点も 2 つ用意する。1 つで済ませると $n=3$ のところで連鎖が切れる。

例：連続する 3 整数の積

$n(n+1)(n+2)$ が $6$ の倍数であることを示す。

$n=1$ のとき $1\cdot 2\cdot 3=6$。

$n=k$ を仮定し、共通部分の $(k+1)(k+2)$ でくくる。

$$(k+1)(k+2)(k+3)=k(k+1)(k+2)+3(k+1)(k+2)$$

第 1 項は仮定から $6$ の倍数。第 2 項の $(k+1)(k+2)$ は連続する 2 整数の積で偶数だから、$3$ をかけて $6$ の倍数になります。

$n^3-n=(n-1)n(n+1)$ なので、型 1 の最初の例と中身は同じもの。並べ方を変えると別の問題に見えます。

$n$ が 1 増えたときに何が保たれるか。倍数なら分けかた、数列なら漸化式、数え上げなら場合分けが、そのまま帰納の段階になります。