数学的帰納法(整除)

方針

解答

⓪ 発想 — どう考え始めるか。 「$5$ の倍数である」ことを全部の $n$ で示す — 倍数性も帰納法で運べる。

(I) $n=1$: $6^1-1=5$。確かに $5$ の倍数。

(II) $n=k$ で $6^k-1=5m$($m$ は整数)と書けると仮定する。$6^{k+1}-1$ を、仮定が使える形 — つまり $6^k-1$ が見える形 — にわざと崩すのが勝負どころだ。$6^{k+1}=6\cdot 6^k$ から

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

と変形すれば、$6\cdot 5m+5=5(6m+1)$ で $5$ の倍数。「仮定のかたまりを作り出す変形」が倍数性の帰納法の核心である。

(I) $n=1$ のとき。 $6^1-1=5$ で、$5$ の倍数。成り立つ。

(II) $n=k$ を仮定する。 $6^k-1$ が $5$ の倍数、すなわち整数 $m$ で $6^k-1=5m$ と書けるとする。$n=k+1$ を調べる。

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

(ここで $6\cdot 6^k=6(6^k-1)+6$ を使い、$-1$ と合わせて $+5$ にした。)仮定 $6^k-1=5m$ を代入する。

$$=6\cdot 5m+5=5(6m+1)$$

$6m+1$ は整数なので、$6^{k+1}-1$ は $5$ の倍数。

結論。 (I)(II) より、すべての自然数 $n$ で $6^n-1$ は $5$ の倍数。

まとめ:整除の帰納法は「$6^{k+1}-1$ を $6^k-1$ でくくり出す」変形がカギ。$6^{k+1}-1=6(6^k-1)+5$ とすれば、仮定($5$ の倍数)と残り($+5$)が両方 $5$ の倍数になる。

発展 — 一歩先へ。 本解の変形 $6^{k+1}-1=6(6^k-1)+5$ は、「余りだけ見れば $6\equiv 1$ だから $6^n\equiv 1^n=1$」という合同式(数A)の考えを、帰納法の言葉に翻訳したものだ。合同式を学んだ人なら $6^n-1\equiv 0(\mathrm{mod}5)$ の $1$ 行で済む — 同じ事実に、帰納法・因数分解・合同式の $3$ つの道がある。

「$a^n-b^n$ は $a-b$ の倍数」という一般形も、別解と同じ因数分解で証明できる。整数の倍数性の問題では、この恒等式が隠れた主役になっていることが多い。

別解

帰納法を使わない一撃の証明が、因数分解でできる。

等比数列の和の公式を因数分解の形で読むと

$$6^n-1=(6-1)(6^{n-1}+6^{n-2}+\cdots +6+1)=5\times (\text{整数})$$

カッコの中は $6$ のべきの和 — 明らかに整数だ。よって $6^n-1$ は $5$ の倍数。これで終わり。

$x^n-1=(x-1)(x^{n-1}+\cdots +1)$ という恒等式に $x=6$ を入れただけである。同じ理屈で「$7^n-1$ は $6$ の倍数」「$10^n-1$($99\cdots 9$)は $9$ の倍数」も一瞬で出る。

直感的に言えば、$6$ 進法で $6^n-1$ は $55\cdots 5$($5$ が $n$ 個)— $10$ 進法の $99\cdots 9$ が $9$ の倍数であるのと同じ景色だ。帰納法は万能の重機、因数分解は急所を突く小刀 — 両方持っていると証明の選択肢が広がる。