「$n^3 - n$ は $6$ の倍数」「$7^n - 1$ は $6$ の倍数」のように、ある式が特定の整数の倍数であることを証明する問題は入試の定番です。帰納法の仮定を上手に活用し、倍数条件を式変形で導く技術を身につけましょう。
「$A$ が $m$ の倍数」とは「$A = m \cdot q$（$q$ は整数）」と表せることです。帰納法で倍数性を示す基本戦略は次の通りです。
命題：すべての自然数 $n$ に対して $f(n)$ は $m$ の倍数である。
[Step 1] $n = 1$ のとき $f(1)$ が $m$ の倍数であることを確認。
[Step 2] $f(k) = mq$（$q$ は整数）と仮定し、$f(k+1)$ を変形して $f(k+1) = m \cdot (\text{整数})$ を示す。
※ 鍵は $f(k+1)$ の式から $f(k)$ を含む形を作り出すことです。
$f(k+1) - f(k)$ が $m$ の倍数であることを示すか、$f(k+1)$ を $f(k)$ を含む形に変形して仮定を代入します。
例：$f(k+1) = \alpha \cdot f(k) + (\text{$m$ の倍数})$ の形にできれば、仮定より $f(k) = mq$ なので $f(k+1) = \alpha \cdot mq + m \cdot r = m(\alpha q + r)$。
✗ $f(k+1) = 6 \cdot \frac{k}{2}$ だから $6$ の倍数（$\frac{k}{2}$ は整数とは限らない！）
✓ $f(k+1) = 6 \cdot q$（$q$ は整数）の形まで確認する
「$m$ の倍数」は「$m \times$（整数）」です。掛けられる側が整数であることを必ず確認しましょう。
$a^n - 1$ や $a^n - b^n$ が特定の数の倍数であることを帰納法で示すパターンは最も基本的です。
命題：すべての自然数 $n$ に対して $7^n - 1$ は $6$ の倍数であることを示せ。
[Step 1] $n = 1$：$7^1 - 1 = 6 = 6 \cdot 1$。$6$ の倍数。
[Step 2] $n = k$ で $7^k - 1 = 6q$（$q$ は整数）と仮定する。
$$7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(7^k - 1) + 7 - 1 = 7 \cdot 6q + 6 = 6(7q + 1)$$
$7q + 1$ は整数なので $7^{k+1} - 1$ は $6$ の倍数。 $\square$
$a^{k+1} = a \cdot a^k$ と変形し、$a^k$ の部分に仮定を使えるようにします。
$a \cdot a^k - b = a(a^k - b) + a \cdot b - b = a(a^k - b) + b(a - 1)$
このように「仮定を使える部分」と「残りの部分」に分解するのがポイントです。
[Step 1] $n = 1$：$5^1 + 3 = 8 = 4 \cdot 2$。$4$ の倍数。
[Step 2] $n = k$ で $5^k + 3 = 4q$（$q$ は整数）と仮定する。
$$5^{k+1} + 3 = 5 \cdot 5^k + 3 = 5(5^k + 3) - 15 + 3 = 5 \cdot 4q - 12 = 4(5q - 3)$$
$5q - 3$ は整数なので $5^{k+1} + 3$ は $4$ の倍数。 $\square$
$n^3 - n$ や $n(n+1)(2n+1)$ のように、$n$ の多項式が特定の数の倍数であることを帰納法で示します。
命題：すべての自然数 $n$ に対して $n^3 - n$ は $6$ の倍数であることを示せ。
[Step 1] $n = 1$：$1^3 - 1 = 0 = 6 \cdot 0$。$6$ の倍数。
[Step 2] $n = k$ で $k^3 - k = 6q$（$q$ は整数）と仮定する。
$$\begin{aligned}(k+1)^3 - (k+1) &= k^3 + 3k^2 + 3k + 1 - k - 1 \\ &= (k^3 - k) + 3k^2 + 3k \\ &= 6q + 3k(k+1)\end{aligned}$$
$k(k+1)$ は連続する2整数の積なので偶数。よって $3k(k+1) = 6 \cdot \frac{k(k+1)}{2}$。
$(k+1)^3 - (k+1) = 6q + 6 \cdot \frac{k(k+1)}{2} = 6\left(q + \frac{k(k+1)}{2}\right)$
$\frac{k(k+1)}{2}$ は整数なので $6$ の倍数。 $\square$
帰納法の証明中に連続整数の積が現れたら、次の性質を活用しましょう：
$k(k+1)$：連続2整数 → $2$ の倍数
$k(k+1)(k+2)$：連続3整数 → $6$ の倍数
一般に、連続 $r$ 個の整数の積は $r!$ の倍数です。
[Step 1] $n = 1$：$1 \cdot 2 \cdot 3 = 6 = 6 \cdot 1$。$6$ の倍数。
[Step 2] $n = k$ で $k(k+1)(2k+1) = 6q$ と仮定する。
$(k+1)(k+2)(2k+3) = (k+1)\{(2k+1)(k+2) + (k+2) - (k+2) + k(2k+3 - 2k - 1)\}$
直接展開する方が明快：
$(k+1)(k+2)(2k+3) - k(k+1)(2k+1)$
$= (k+1)\{(k+2)(2k+3) - k(2k+1)\}$
$= (k+1)(2k^2+7k+6-2k^2-k)$
$= (k+1)(6k+6) = 6(k+1)(k+1) = 6(k+1)^2$
よって $(k+1)(k+2)(2k+3) = 6q + 6(k+1)^2 = 6(q + (k+1)^2)$。$6$ の倍数。 $\square$
仮定 $f(k) = mq$ を「$f(k)$ の式を $q$ で表す」形に変形して代入するテクニックです。
命題：奇数 $n \geq 1$ に対して $4^n + 5^n + 6^n$ は $15$ の倍数であることを示せ。
[Step 1] $n = 1$：$4+5+6 = 15 = 15 \cdot 1$。成り立つ。
[Step 2] 奇数 $k$ で $4^k + 5^k + 6^k = 15q$ と仮定。次の奇数 $k+2$ を考える。
$4^{k+2} + 5^{k+2} + 6^{k+2}$
$= 16 \cdot 4^k + 25 \cdot 5^k + 36 \cdot 6^k$
仮定より $4^k = 15q - 5^k - 6^k$ なので：
$= 16(15q - 5^k - 6^k) + 25 \cdot 5^k + 36 \cdot 6^k$
$= 16 \cdot 15q + 9 \cdot 5^k + 20 \cdot 6^k$
$= 15 \cdot 16q + 9 \cdot 5^k + 20 \cdot 6^k$
$9 \cdot 5^k + 20 \cdot 6^k = 15 \cdot 3 \cdot 5^{k-1} + 15 \cdot 4 \cdot 6^{k-1} \cdot \frac{20}{15} \cdot \ldots$
（別の方法：$= 15(16q) + 9 \cdot 5^k + 20 \cdot 6^k$。$9 \cdot 5 + 20 \cdot 6 = 45 + 120 = 165 = 15 \cdot 11$。$k$ が奇数のとき一般に $15$ の倍数。）
仮定 $f(k) = mq$ から、$f(k)$ に含まれる項を $q$ を使って表す：
例1：$a^k = mq - b^k$ のように、特定の項を他の項で置き換える
例2：$a^k \equiv r \pmod{m}$ と合同式で仮定を書き直す
※ 合同式を使うと見通しがよくなることが多いです。
✗ 「$n = k$ のとき成立」→「$n = k+1$ のとき」と進める（$k+1$ は偶数！）
✓ 「奇数 $n = k$ のとき」→「次の奇数 $n = k+2$ のとき」と進める
命題の対象が「すべての奇数」なら、帰納的ステップは $k \to k+2$ です。
二項定理を使って $a^n$ を展開し、倍数性を導く方法も重要です。
$6^n = (5+1)^n = \sum_{r=0}^{n} \binom{n}{r} 5^r = 1 + 5n + \binom{n}{2}5^2 + \cdots + 5^n$
$6^n - 1 = 5n + \binom{n}{2}5^2 + \cdots + 5^n = 5\left(n + \binom{n}{2} \cdot 5 + \cdots + 5^{n-1}\right)$
括弧内は整数なので $6^n - 1$ は $5$ の倍数。
（帰納法を使わずに一撃で証明できる！）
命題：$n \geq 1$ のとき $n^3 + 5n$ は $6$ の倍数であることを示せ。
[Step 1] $n = 1$：$1 + 5 = 6 = 6 \cdot 1$。成り立つ。
[Step 2] $n = k$ で $k^3 + 5k = 6q$ と仮定する。
$(k+1)^3 + 5(k+1) = k^3 + 3k^2 + 3k + 1 + 5k + 5$
$= (k^3 + 5k) + 3k^2 + 3k + 6 = 6q + 3k(k+1) + 6$
$k(k+1)$ は偶数なので $3k(k+1) = 6 \cdot \frac{k(k+1)}{2}$。
$(k+1)^3 + 5(k+1) = 6q + 6 \cdot \frac{k(k+1)}{2} + 6 = 6\left(q + \frac{k(k+1)}{2} + 1\right)$
$6$ の倍数。 $\square$
倍数証明には帰納法以外の方法もあります：
$n^3 - n = n(n-1)(n+1) = $ 連続3整数の積 → $6$ の倍数（因数分解で直接証明）
$a^n - 1 = (a-1)(a^{n-1} + \cdots + 1)$ → $a-1$ の倍数（因数分解で直接証明）
問題文に「帰納法で証明せよ」と指定がなければ、最も簡潔な方法を選びましょう。
$7 \equiv 1 \pmod{6}$ より $7^n \equiv 1^n = 1 \pmod{6}$ なので $7^n - 1 \equiv 0 \pmod{6}$。
合同式に慣れると、帰納法よりも遥かに簡潔に証明できる場合があります。ただし「帰納法で示せ」と指定された場合は帰納法を使いましょう。
Q1. $5^n - 1$ が $4$ の倍数であることの基底段階を確認せよ。
Q2. $7^{k+1} - 1$ を $7^k - 1$ を含む形に変形せよ。
Q3. $k(k+1)$ が必ず偶数である理由を述べよ。
Q4. $n^3 + 5n$ の帰納法で $(k+1)^3 + 5(k+1) - (k^3 + 5k)$ を計算せよ。
Q5. 合同式で $8^n \equiv (\quad) \pmod{7}$ を求めよ。
すべての自然数 $n$ に対して $8^n - 1$ は $7$ の倍数であることを数学的帰納法で証明せよ。
[Step 1] $n = 1$：$8^1 - 1 = 7 = 7 \cdot 1$。$7$ の倍数。
[Step 2] $n = k$ で $8^k - 1 = 7q$（$q$ は整数）と仮定する。
$8^{k+1} - 1 = 8 \cdot 8^k - 1 = 8(8^k - 1) + 8 - 1 = 8 \cdot 7q + 7 = 7(8q + 1)$
$8q + 1$ は整数なので $7$ の倍数。 $\square$
すべての自然数 $n$ に対して $n^5 - n$ は $5$ の倍数であることを数学的帰納法で証明せよ。
[Step 1] $n = 1$：$1 - 1 = 0 = 5 \cdot 0$。$5$ の倍数。
[Step 2] $n = k$ で $k^5 - k = 5q$ と仮定する。
$(k+1)^5 - (k+1) = k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 - k - 1$
$= (k^5 - k) + 5k^4 + 10k^3 + 10k^2 + 5k$
$= 5q + 5(k^4 + 2k^3 + 2k^2 + k) = 5(q + k^4 + 2k^3 + 2k^2 + k)$
括弧内は整数なので $5$ の倍数。 $\square$
二項定理で $(k+1)^5$ を展開すると、$\binom{5}{1}k^4 = 5k^4$, $\binom{5}{2}k^3 = 10k^3$ など、$k^5$ 以外の項はすべて $5$ の倍数です。これがフェルマーの小定理の初等的証明と同じ構造です。
すべての自然数 $n$ に対して $3^{2n} - 1$ は $8$ の倍数であることを数学的帰納法で証明せよ。
[Step 1] $n = 1$：$3^2 - 1 = 8 = 8 \cdot 1$。$8$ の倍数。
[Step 2] $n = k$ で $3^{2k} - 1 = 8q$（$q$ は整数）と仮定する。すなわち $9^k - 1 = 8q$。
$9^{k+1} - 1 = 9 \cdot 9^k - 1 = 9(9^k - 1) + 9 - 1 = 9 \cdot 8q + 8 = 8(9q + 1)$
$9q + 1$ は整数なので $8$ の倍数。 $\square$
$3^{2n} = 9^n$ と見ることで、$a^n - 1$ の標準形に帰着できます。$9 \equiv 1 \pmod{8}$ なので $9^n \equiv 1 \pmod{8}$。
すべての自然数 $n$ に対して $11^{n+2} + 12^{2n+1}$ は $133$ の倍数であることを数学的帰納法で証明せよ。
[Step 1] $n = 1$：$11^3 + 12^3 = 1331 + 1728 = 3059 = 133 \times 23$。$133$ の倍数。
[Step 2] $n = k$ で $11^{k+2} + 12^{2k+1} = 133q$（$q$ は整数）と仮定する。
$n = k+1$ のとき：$11^{k+3} + 12^{2k+3}$
$= 11 \cdot 11^{k+2} + 144 \cdot 12^{2k+1}$
$= 11 \cdot 11^{k+2} + 11 \cdot 12^{2k+1} + 133 \cdot 12^{2k+1}$
$= 11(11^{k+2} + 12^{2k+1}) + 133 \cdot 12^{2k+1}$
$= 11 \cdot 133q + 133 \cdot 12^{2k+1} = 133(11q + 12^{2k+1})$
$11q + 12^{2k+1}$ は整数なので $133$ の倍数。 $\square$
$144 = 11 + 133$ と分解する着想がポイントです。$12^2 = 144$ の中から $11$ と $133$ を取り出すことで、仮定の形と $133$ の倍数の両方を同時に作り出しています。なお $133 = 7 \times 19$ です。