数学的帰納法(倍数の証明)

方針

解答

⓪ 発想 — どう考え始めるか。 「すべての自然数 $n$ で $n^3+2n$ が $3$ の倍数」を帰納法で示す。

倍数の帰納法では、$n=k+1$ の式と $n=k$ の式の「差」を作るのが定石。

$(k+1{)}^3+2(k+1)$ から $k^3+2k$ を引くと、うまく $3$ でくくれる形が出るはず。

その差が $3$ の倍数なら、仮定「$k$ の式が $3$ の倍数」に足して、$k+1$ の式も $3$ の倍数になる。

① 出発点。 $n=1$ のとき $1^3+2\cdot 1=3$。$3$ の倍数。

② 仮定と差。 $n=k$ で $k^3+2k$ が $3$ の倍数と仮定する。$n=k+1$ の式との差を計算する。

$$\{(k+1{)}^3+2(k+1)\}-(k^3+2k)=(k^3+3k^2+3k+1+2k+2)-(k^3+2k)$$ $$=3k^2+3k+3=3(k^2+k+1)$$

これは $3$ の倍数。

③ $n=k+1$ を導く。 よって

$$(k+1{)}^3+2(k+1)=\underset{3\text{の倍数(仮定)}}{\underbrace{(k^3+2k)}}+\underset{3\text{の倍数}}{\underbrace{3(k^2+k+1)}}$$

$3$ の倍数どうしの和だから $3$ の倍数。$n=k+1$ でも成立。

④ 結論。 (i)(ii) より、すべての自然数 $n$ で $n^3+2n$ は $3$ の倍数。(証明終)

まとめ:倍数の帰納法は「$k+1$ の式 $-$ $k$ の式 $=$ $3$ の倍数」を示す。差 $3(k^2+k+1)$ が $3$ でくくれれば、仮定に足して $k+1$ でも $3$ の倍数。差をとるのが計算のコツ。

発展 — 一歩先へ。 じつは帰納法を使わずとも、$n^3+2n=n^3-n+3n=(n-1)n(n+1)+3n$ と変形すれば一目で分かる。連続 $3$ 整数の積は必ず $3$ の倍数、$3n$ も $3$ の倍数だからだ。

背景にあるのはフェルマーの小定理。素数 $p$ について $n^p\equiv n(\mathrm{mod}p)$ が成り立ち、$p=3$ なら $n^3\equiv n$、つまり $n^3-n$ は $3$ の倍数。

$n^3+2n=(n^3-n)+3n$ と見れば、フェルマーの小定理そのものが効いている。倍数の証明は、帰納法・因数分解・合同式のどれでも攻められる。

別解

別解 — $3$ 連続整数の積に化けさせる(得意な人向けの直接証明)。 帰納法を使わず、式変形だけで示せる。

$$n^3+2n=n^3-n+3n=n(n^2-1)+3n=(n-1)n(n+1)+3n.$$

$(n-1)n(n+1)$ は連続する $3$ つの整数の積。連続 $3$ 整数には必ず $3$ の倍数が $1$ つ含まれるので、この積は $3$ の倍数。

残りの $3n$ も当然 $3$ の倍数。$3$ の倍数どうしの和だから $n^3+2n$ は $3$ の倍数。

念のため合同式でも確かめられる。$n\equiv 0,1,2(\mathrm{mod}3)$ で $n^3+2n$ を計算すると、順に $0$、$1+2=3\equiv 0$、$8+4=12\equiv 0$。どの場合も $3$ の倍数。帰納法・因数分解・余りの分類、どれでも同じ結論にたどり着く。