数学的帰納法は、自然数 $n$ に関する命題を証明する強力な手法です。「$n = 1$ で成立」と「$n = k$ で成立すれば $n = k+1$ でも成立」の2つを示すことで、すべての自然数 $n$ に対して命題が成り立つことを保証します。まずは等式の証明から学びましょう。
自然数 $n$ に関する命題 $P(n)$ がすべての自然数で成り立つことを証明するために、数学的帰納法を用います。
次の2つを示せば、すべての自然数 $n$ に対して $P(n)$ が成り立つ。
[I] 基底段階：$P(1)$ が成り立つ。
[II] 帰納段階：$P(k)$ が成り立つと仮定すると、$P(k+1)$ も成り立つ。
※ [II] の仮定「$P(k)$ が成り立つ」を帰納法の仮定と呼びます。
数学的帰納法はドミノ倒しに例えられます。
[I] 最初の1枚目のドミノを倒す（$P(1)$ が成立）。
[II] $k$ 枚目が倒れたら必ず $k+1$ 枚目も倒れる仕組みになっている（$P(k) \Rightarrow P(k+1)$）。
この2つが揃えば、すべてのドミノが倒れます。どちらか一方が欠けても証明は成立しません。
✗ 「$n = k$ で成り立つと仮定する」ということは、まだ証明していない命題を正しいと決めつけているのでは？
✓ 帰納段階で示しているのは「$P(k) \Rightarrow P(k+1)$」という条件付きの命題（含意）です。$P(k)$ 自体の真偽は問題にしていません。「もし成り立つなら」という仮定のもとで論理を進めています。
最も基本的な例として、自然数の和の公式を帰納法で証明します。
命題：すべての自然数 $n$ に対して $\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$
[I] $n = 1$ のとき：
（左辺）$= 1$、（右辺）$= \frac{1 \cdot 2}{2} = 1$。成立。
[II] $n = k$ で成立を仮定：$\displaystyle\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$ ... (*)
$n = k + 1$ のとき：
$$\sum_{i=1}^{k+1} i = \sum_{i=1}^{k} i + (k+1) \overset{(*)}{=} \frac{k(k+1)}{2} + (k+1)$$
$$= \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$$
これは $n = k+1$ のときの右辺と一致。よって $P(k+1)$ も成立。
[I], [II] より、すべての自然数 $n$ で成立。$\square$
帰納段階で最も大切なのは、帰納法の仮定 (*) を実際に使うことです。仮定を使わずに直接 $P(k+1)$ を示しているなら、それは帰納法ではなく直接証明です。
「どこで仮定を使ったか」を明示するために、(*)のようなマークをつけると答案が読みやすくなります。
入試の答案における帰納法の定型的な書き方を身につけましょう。
1行目：「数学的帰納法で証明する。」
[I]：「$n = 1$ のとき（左辺）$= \cdots$,（右辺）$= \cdots$ で成立。」
[II]：「$n = k$ で成立すると仮定する。すなわち ... (*)」
「$n = k + 1$ のとき、（左辺）$= \cdots \overset{(*)}{=} \cdots =$ （右辺）。」
「よって $n = k+1$ でも成立。」
結論：「[I], [II] より、すべての自然数 $n$ に対して成立。」
命題：$\displaystyle\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$ をすべての自然数 $n$ で示せ。
数学的帰納法で証明する。
[I] $n = 1$：（左辺）$= 1$,（右辺）$= \frac{1 \cdot 2 \cdot 3}{6} = 1$。成立。
[II] $n = k$ で $\displaystyle\sum_{i=1}^{k} i^2 = \frac{k(k+1)(2k+1)}{6}$ ... (*) を仮定。
$n = k+1$：
$\displaystyle\sum_{i=1}^{k+1} i^2 = \sum_{i=1}^{k} i^2 + (k+1)^2 \overset{(*)}{=} \frac{k(k+1)(2k+1)}{6} + (k+1)^2$
$= \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} = \frac{(k+1)[k(2k+1) + 6(k+1)]}{6}$
$= \frac{(k+1)(2k^2 + 7k + 6)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}$
$= \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}$ これは $n = k+1$ の場合。成立。
[I], [II] より、すべての自然数 $n$ で成立。$\square$
✗ 「$n = k$ のとき成り立つ」と書いて仮定であることを明示しない
✗ 帰納法の仮定をどこで使ったか分からない
✗ 結論の「[I], [II] より...」を書き忘れる
✓ 「$n = k$ で成立すると仮定する」「仮定 (*) より」「[I], [II] より全ての自然数で成立」を必ず明記する
帰納法で証明できる等式は和の公式だけではありません。積の公式や因数に関する等式も証明できます。
命題：$r \neq 1$ のとき $\displaystyle\sum_{k=0}^{n} r^k = \frac{r^{n+1} - 1}{r - 1}$
[I] $n = 0$：（左辺）$= r^0 = 1$,（右辺）$= \frac{r - 1}{r - 1} = 1$。成立。
[II] $n = k$ で $\displaystyle\sum_{i=0}^{k} r^i = \frac{r^{k+1} - 1}{r - 1}$ ... (*) を仮定。
$n = k+1$：
$\displaystyle\sum_{i=0}^{k+1} r^i = \sum_{i=0}^{k} r^i + r^{k+1} \overset{(*)}{=} \frac{r^{k+1} - 1}{r - 1} + r^{k+1}$
$= \frac{r^{k+1} - 1 + r^{k+1}(r-1)}{r-1} = \frac{r^{k+1} - 1 + r^{k+2} - r^{k+1}}{r-1} = \frac{r^{k+2} - 1}{r-1}$
$n = k+1$ のときの式と一致。成立。[I], [II] より証明完了。$\square$
命題：$\displaystyle\prod_{k=1}^{n}\left(1 + \frac{1}{k}\right) = n + 1$ をすべての自然数 $n$ で示せ。
[I] $n = 1$：（左辺）$= 1 + \frac{1}{1} = 2$,（右辺）$= 2$。成立。
[II] $n = k$ で $\displaystyle\prod_{i=1}^{k}\left(1 + \frac{1}{i}\right) = k + 1$ ... (*) を仮定。
$n = k+1$：
$\displaystyle\prod_{i=1}^{k+1}\left(1 + \frac{1}{i}\right) = \prod_{i=1}^{k}\left(1 + \frac{1}{i}\right) \cdot \left(1 + \frac{1}{k+1}\right) \overset{(*)}{=} (k+1) \cdot \frac{k+2}{k+1} = k + 2$
$n = k+1$ のときの右辺と一致。成立。$\square$
等式の帰納法の帰納段階は、ほぼ次の形に統一されます。
和の場合：$\sum_{k=1}^{n+1} f(k) = \sum_{k=1}^{n} f(k) + f(n+1) \overset{(*)}{=} (\text{仮定の右辺}) + f(n+1) = (\text{目標の右辺})$
積の場合：$\prod_{k=1}^{n+1} f(k) = \prod_{k=1}^{n} f(k) \cdot f(n+1) \overset{(*)}{=} (\text{仮定の右辺}) \times f(n+1) = (\text{目標の右辺})$
帰納法は万能ではありません。使うべき場面と他の方法が適切な場面を見極めましょう。
1. 「すべての自然数 $n$ で示せ」「$n$ で証明せよ」と問題文にある場合。
2. 等式の左辺が $\sum$ や $\prod$ で、$n$ から $n+1$ への差分が計算しやすい場合。
3. 命題の「公式」が与えられているが、それを直接導出するのが難しい場合。
4. 漸化式的な構造がある場合（$n$ に関する帰納的な定義がある）。
✗ 帰納法で一般項を「発見」しようとする → 帰納法は「与えられた命題を検証」する手法であり、命題を見つける手法ではない
✓ まず予想を立て（具体的な $n$ で計算する、差分を調べるなど）、その予想を帰納法で証明するのが正しい使い方
帰納法には「何を証明するか」という目標（ゴール）が必要です。ゴールなしに帰納法を始めることはできません。
例：$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ は帰納法を使わなくても証明できます。
$S = 1 + 2 + \cdots + n$ と $S = n + (n-1) + \cdots + 1$ を加えると $2S = n(n+1)$ より $S = \frac{n(n+1)}{2}$。
この「逆順に足す」方法はガウスの方法として知られ、帰納法より直接的です。問題が「帰納法で示せ」と指定していなければ、直接的な方法の方が望ましいこともあります。
Q1. 数学的帰納法の2つのステップは何か。
Q2. 帰納法で $\sum_{k=1}^{n} (2k-1) = n^2$ を証明するとき、帰納段階で何を仮定し、何を示すか。
Q3. 帰納法の仮定を使わずに $P(k+1)$ を示した場合、問題はあるか。
Q4. 基底段階 [I] を省略するとどうなるか。
Q5. $P(n)$：$n^2 + n$ は偶数。これを帰納法で示す場合の帰納段階を書け。
数学的帰納法を用いて、すべての自然数 $n$ に対して次の等式を証明せよ。
$$\sum_{k=1}^{n} k^3 = \left\{\frac{n(n+1)}{2}\right\}^2$$
[I] $n = 1$：（左辺）$= 1$,（右辺）$= 1^2 = 1$。成立。
[II] $n = k$ で $\sum_{i=1}^{k} i^3 = \left\{\frac{k(k+1)}{2}\right\}^2$ ... (*) を仮定。
$n = k+1$：
$\sum_{i=1}^{k+1} i^3 \overset{(*)}{=} \left\{\frac{k(k+1)}{2}\right\}^2 + (k+1)^3 = \frac{k^2(k+1)^2}{4} + (k+1)^3$
$= \frac{(k+1)^2[k^2 + 4(k+1)]}{4} = \frac{(k+1)^2(k^2+4k+4)}{4} = \frac{(k+1)^2(k+2)^2}{4}$
$= \left\{\frac{(k+1)(k+2)}{2}\right\}^2$。$n = k+1$ のときの右辺と一致。
[I], [II] より、すべての自然数 $n$ で成立。$\square$
数学的帰納法を用いて、すべての自然数 $n$ に対して次の等式を証明せよ。
$$\sum_{k=1}^{n} \frac{1}{k(k+1)} = \frac{n}{n+1}$$
[I] $n = 1$：（左辺）$= \frac{1}{1 \cdot 2} = \frac{1}{2}$,（右辺）$= \frac{1}{2}$。成立。
[II] $n = k$ で $\sum_{i=1}^{k} \frac{1}{i(i+1)} = \frac{k}{k+1}$ ... (*) を仮定。
$n = k+1$：
$\sum_{i=1}^{k+1} \frac{1}{i(i+1)} \overset{(*)}{=} \frac{k}{k+1} + \frac{1}{(k+1)(k+2)}$
$= \frac{k(k+2) + 1}{(k+1)(k+2)} = \frac{k^2 + 2k + 1}{(k+1)(k+2)} = \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2}$。成立。
[I], [II] より、すべての自然数 $n$ で成立。$\square$
帰納段階のポイントは通分して整理する部分です。分子が完全平方式 $(k+1)^2$ になり、$(k+1)$ で約分できることが鍵です。なお、この等式は部分分数分解 $\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}$ を使った望遠鏡和でも直接証明できます。
$a_1 = 1$, $a_{n+1} = 3a_n + 2$ で定められる数列について、$a_n = 2 \cdot 3^{n-1} - 1$ をすべての自然数 $n$ で証明せよ。
[I] $n = 1$：$a_1 = 1$, $2 \cdot 3^0 - 1 = 1$。成立。
[II] $n = k$ で $a_k = 2 \cdot 3^{k-1} - 1$ ... (*) を仮定。
$n = k+1$：漸化式より
$a_{k+1} = 3a_k + 2 \overset{(*)}{=} 3(2 \cdot 3^{k-1} - 1) + 2 = 2 \cdot 3^k - 3 + 2 = 2 \cdot 3^k - 1$
$= 2 \cdot 3^{(k+1)-1} - 1$。$n = k+1$ のときの式と一致。
[I], [II] より、すべての自然数 $n$ で $a_n = 2 \cdot 3^{n-1} - 1$。$\square$
漸化式で定義された数列の一般項を帰納法で証明する典型パターンです。帰納段階では漸化式 $a_{k+1} = 3a_k + 2$ に仮定 (*) を代入するだけで自然に $P(k+1)$ が導かれます。
数学的帰納法を用いて、すべての自然数 $n$ に対して次の等式を証明せよ。
$$\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$$
ただし、$\binom{2(k+1)}{k+1} = \frac{2(2k+1)}{k+1}\binom{2k}{k}$ を用いてよい。
[I] $n = 1$：（左辺）$= \binom{1}{0}^2 + \binom{1}{1}^2 = 1 + 1 = 2$,（右辺）$= \binom{2}{1} = 2$。成立。
[II] $n = m$ で $\sum_{k=0}^{m}\binom{m}{k}^2 = \binom{2m}{m}$ ... (*) を仮定。
$n = m+1$：パスカルの法則 $\binom{m+1}{k} = \binom{m}{k} + \binom{m}{k-1}$ を利用する。
$\sum_{k=0}^{m+1}\binom{m+1}{k}^2 = \sum_{k=0}^{m+1}\left(\binom{m}{k} + \binom{m}{k-1}\right)^2$
$= \sum_{k=0}^{m+1}\binom{m}{k}^2 + 2\sum_{k=0}^{m+1}\binom{m}{k}\binom{m}{k-1} + \sum_{k=0}^{m+1}\binom{m}{k-1}^2$
ヴァンデルモンドの恒等式 $\sum_{k=0}^{n}\binom{m}{k}\binom{m}{n-k} = \binom{2m}{n}$ を用いると、
第1項 $+$ 第3項 $= 2\binom{2m}{m}$, 第2項 $= 2\binom{2m}{m-1}$ であることが示せます。
$2\binom{2m}{m} + 2\binom{2m}{m-1} = 2\binom{2m}{m} + 2 \cdot \frac{m}{m+1}\binom{2m}{m}$
$= 2\binom{2m}{m}\left(1 + \frac{m}{m+1}\right) = 2\binom{2m}{m} \cdot \frac{2m+1}{m+1} = \binom{2(m+1)}{m+1}$
ヒントの等式を使用。[I], [II] より成立。$\square$
この等式はヴァンデルモンドの恒等式の特殊ケースとしても知られます。帰納法の証明は技巧的ですが、パスカルの法則と与えられたヒントを適切に組み合わせることが鍵です。組合せ論的な証明（$2n$ 人から $n$ 人を選ぶ方法を2グループに分けて数える）の方がエレガントとも言えます。