通常の帰納法（$n = k$ の仮定から $n = k+1$ を示す）だけでなく、強い帰納法（完全帰納法）や、$n = k$ と $n = k-1$ の2つを仮定する方法など、帰納法には様々な変形があります。数列だけでなく図形やアルゴリズムへの応用も学びましょう。
通常の帰納法では $n = k$ のみを仮定しますが、強い帰納法では $n = 1, 2, \ldots, k$ のすべてを仮定します。
[Step 1] $n = 1$ のとき $P(1)$ が成り立つ。
[Step 2] $n = 1, 2, \ldots, k$ のすべてで $P(n)$ が成り立つと仮定し、$P(k+1)$ を示す。
※ $P(k+1)$ の証明に $P(k)$ 以外の $P(j)$（$j < k$）も使える点が強力です。
命題：$F_1 = 1$, $F_2 = 1$, $F_{n+2} = F_{n+1} + F_n$ で定義されるフィボナッチ数列について、すべての $n \geq 1$ で $F_n < 2^n$ を示せ。
[Step 1] $n = 1$：$F_1 = 1 < 2^1 = 2$。$n = 2$：$F_2 = 1 < 2^2 = 4$。成り立つ。
[Step 2] $n = 1, 2, \ldots, k$（$k \geq 2$）で $F_n < 2^n$ が成り立つと仮定する。
$$F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} = 2^{k-1}(2+1) = 3 \cdot 2^{k-1} < 4 \cdot 2^{k-1} = 2^{k+1}$$
よって $F_{k+1} < 2^{k+1}$ が成り立つ。 $\square$
フィボナッチ数列の漸化式は $F_{n+2} = F_{n+1} + F_n$ なので、$F_{k+1}$ の評価には $F_k$ だけでなく $F_{k-1}$ の情報も必要です。
通常の帰納法（$n = k$ のみ仮定）では $F_{k-1}$ について何も言えないため、強い帰納法を使います。
✗ 2段階の漸化式なのに $n = 1$ だけ確認して $n = 2$ を飛ばす
✓ 漸化式が2項前まで参照するなら、$n = 1$ と $n = 2$ の両方を確認する
$F_{k+1} = F_k + F_{k-1}$ を使うには $k \geq 2$ が必要。よって $n = 1, 2$ を基底段階で確認します。
$n = k$ と $n = k-1$ の2つを仮定して $n = k+1$ を示す方法は、3項間漸化式で定義された数列に有効です。
命題：$a_1 = 1$, $a_2 = 3$, $a_{n+2} = 3a_{n+1} - 2a_n$ のとき $a_n = 2^n - 1$ を示せ。
[Step 1] $n = 1$：$a_1 = 1 = 2^1 - 1$。$n = 2$：$a_2 = 3 = 2^2 - 1$。成り立つ。
[Step 2] $n = k$, $n = k+1$ で $a_k = 2^k - 1$, $a_{k+1} = 2^{k+1} - 1$ と仮定する。
$$\begin{aligned}a_{k+2} &= 3a_{k+1} - 2a_k = 3(2^{k+1}-1) - 2(2^k - 1) \\ &= 3 \cdot 2^{k+1} - 3 - 2^{k+1} + 2 \\ &= 2 \cdot 2^{k+1} - 1 = 2^{k+2} - 1\end{aligned}$$
よって $n = k+2$ でも成り立つ。 $\square$
[Step 1] $n = 1$, $n = 2$ で命題を確認
[Step 2] $n = k$, $n = k+1$ の両方を仮定し、$n = k+2$ を示す
※ 3項間漸化式 $a_{n+2} = pa_{n+1} + qa_n$ の一般項検証に最適な方法です。
2段階帰納法は強い帰納法の特殊ケースです。$P(1), \ldots, P(k)$ のうち $P(k-1)$ と $P(k)$ だけ使うなら、2段階帰納法として記述する方が明快です。
入試の答案では「$n = k$, $k+1$ で成り立つと仮定」と書けば十分です。
帰納法は数列以外にも適用できます。図形の分割問題は代表例です。
命題：$n$ 本の直線（どの2本も平行でなく、どの3本も1点で交わらない）で平面を分割すると、領域の数は $\frac{n^2+n+2}{2}$ 個であることを示せ。
[Step 1] $n = 1$：1本の直線で平面は $2$ 領域。$\frac{1+1+2}{2} = 2$。成り立つ。
[Step 2] $n = k$ で $\frac{k^2+k+2}{2}$ 領域と仮定する。$k+1$ 本目の直線を引くと：
新しい直線は既存の $k$ 本と $k$ 個の交点を持つ（どの2本も平行でなく3本が1点で交わらないため）。
これらの $k$ 個の交点により、新しい直線は $k+1$ 個の部分に分割される。各部分が既存の1領域を2つに分けるので、領域は $k+1$ 個増加する。
$$\frac{k^2+k+2}{2} + (k+1) = \frac{k^2+k+2+2k+2}{2} = \frac{k^2+3k+4}{2} = \frac{(k+1)^2+(k+1)+2}{2}$$
よって $n = k+1$ でも成り立つ。 $\square$
命題：凸 $n$ 角形（$n \geq 3$）は対角線によって $n - 2$ 個の三角形に分割できることを示せ。
[Step 1] $n = 3$：三角形はそのまま $1 = 3-2$ 個の三角形。成り立つ。
[Step 2] $3 \leq m \leq k$ のすべての凸 $m$ 角形で成り立つと仮定する（強い帰納法）。
凸 $(k+1)$ 角形の1辺を選び、その辺の両端を $A$, $B$ とする。$A$, $B$ と隣り合わない頂点 $C$ を選び、対角線 $AC$, $BC$ を引くと：
三角形 $ABC$ と、$AC$ の一方の側の凸 $p$ 角形、$BC$ の一方の側の凸 $q$ 角形に分かれる（$p + q = k + 2$）。
（より簡潔な証明：辺 $AB$ の向かい側の任意の頂点 $P$ を取り、対角線 $AP$ を引くと、凸 $r$ 角形と凸 $s$ 角形に分かれ $r + s = k + 3$。仮定より $(r-2) + (s-2) = r+s-4 = k-1 = (k+1)-2$。）
図形の帰納法では「$n$ を $1$ 増やすと何が変わるか」を明確にすることが重要です。
直線の追加→交点の数→領域の増加、のように因果関係を丁寧に追います。
帰納法は「すべての $n$ に対してある性質をもつものが存在する」ことの証明にも使えます。
命題：すべての自然数 $n$ は $n = \sum_{i=0}^{k} a_i \cdot 2^i$（$a_i \in \{0, 1\}$）の形に表せる（2進法表記の存在）。
[Step 1] $n = 1$：$1 = 1 \cdot 2^0$。成り立つ。
[Step 2] $1$ 以上 $k$ 以下のすべての自然数で成り立つと仮定（強い帰納法）。
$k + 1$ が偶数のとき：$k + 1 = 2m$（$1 \leq m \leq k$）。仮定より $m$ は2進表記可能。$m = \sum a_i 2^i$ のとき $k+1 = \sum a_i 2^{i+1}$。
$k + 1$ が奇数のとき：$k + 1 = 2m + 1$（$1 \leq m \leq k$ または $m = 0$）。$m = 0$ なら $k+1 = 1$（既に確認済み）。$m \geq 1$ なら仮定より $m$ は2進表記可能で $k+1 = 1 + \sum a_i 2^{i+1}$。 $\square$
帰納法は「すべての自然数で○○が成り立つ」を示す手法です。○○の部分は等式・不等式・倍数性・存在性など、何でも構いません。
「すべての $n$ に対して、ある表現が存在する」のように存在量化子を含む命題にも帰納法は有効です。
✗ 「$n$ 頭の馬はすべて同じ色」→「$n+1$ 頭でも同じ色」（$n = 1 \to 2$ で失敗する有名な誤り）
✓ 帰納法のステップが「すべての $k$」で正しく機能するか確認する
$n = 1$ から $n = 2$ への推移で、「2頭のうちどの1頭をとっても同じ色」は「2頭が同じ色」を意味しません。帰納的ステップの論理的飛躍に注意しましょう。
帰納法は万能ではありません。帰納法が不向きな場面を知ることも重要です。
帰納法が有効：命題が自然数（または整数）$n$ でパラメータ化されており、$P(k) \Rightarrow P(k+1)$ の論理的連鎖を作れる場合
帰納法が不向き：$P(k)$ から $P(k+1)$ への橋渡しが見つからない場合、または直接証明の方が簡潔な場合
※ 帰納法は「示すべきことがわかっているが直接示せない」ときに特に有効です。
帰納法が最適：$\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$（右辺の式を「見つける」のは難しいが、与えられれば帰納法で検証可能）
直接証明が最適：$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$（ガウスの方法やシグマの性質で直接導出可能）
帰納法で「発見」はできない：帰納法は $P(n)$ の内容が既に与えられている必要がある。「一般項を求めよ」に帰納法は使えない（検証には使える）。
1. 証明：与えられた等式・不等式・性質を証明する（最も基本的な使い方）
2. 検証：予想された一般項や公式が正しいことを確認する
3. 構成：帰納的に対象を構成し、その存在を示す
Q1. 強い帰納法と通常の帰納法の違いを一言で述べよ。
Q2. フィボナッチ数列の性質の証明で、基底段階を $n = 1$ と $n = 2$ の両方で確認する理由は何か。
Q3. $n$ 本の直線が平面を最大何領域に分割するか。$n = 4$ で計算せよ。
Q4. 「すべての馬は同じ色」の誤った帰納法は、どのステップで破綻しているか。
Q5. 帰納法が「発見」の道具にならない理由を述べよ。
$a_1 = 2$, $a_2 = 5$, $a_{n+2} = 5a_{n+1} - 6a_n$ で定義される数列について、$a_n = 3^n - 2^n$ を数学的帰納法で証明せよ。
[Step 1] $n = 1$：$3^1 - 2^1 = 1$... ではなく $a_1 = 2$ で、$3 - 2 = 1 \neq 2$。
再確認：$a_1 = 2$, $3^1 - 2^1 = 1$。一致しない。
（問題の数列を修正：$a_1 = 1$, $a_2 = 5$ とすると $3^1 - 2^1 = 1$, $3^2 - 2^2 = 5$ で一致。）
$a_1 = 1$, $a_2 = 5$ とする。$n = 1$：$3-2 = 1 = a_1$ ✓。$n = 2$：$9-4 = 5 = a_2$ ✓。
[Step 2] $a_k = 3^k - 2^k$, $a_{k+1} = 3^{k+1} - 2^{k+1}$ と仮定する。
$a_{k+2} = 5a_{k+1} - 6a_k = 5(3^{k+1}-2^{k+1}) - 6(3^k - 2^k)$
$= 5 \cdot 3^{k+1} - 5 \cdot 2^{k+1} - 6 \cdot 3^k + 6 \cdot 2^k$
$= 3^k(15 - 6) - 2^k(10 - 6) = 9 \cdot 3^k - 4 \cdot 2^k = 3^{k+2} - 2^{k+2}$ $\square$
フィボナッチ数列 $F_1 = 1$, $F_2 = 1$, $F_{n+2} = F_{n+1} + F_n$ について、$F_1 + F_2 + \cdots + F_n = F_{n+2} - 1$ を数学的帰納法で証明せよ。
[Step 1] $n = 1$：左辺 $= F_1 = 1$、右辺 $= F_3 - 1 = 2 - 1 = 1$。成り立つ。
[Step 2] $n = k$ で $\sum_{i=1}^{k} F_i = F_{k+2} - 1$ と仮定する。
$\sum_{i=1}^{k+1} F_i = \sum_{i=1}^{k} F_i + F_{k+1} = (F_{k+2} - 1) + F_{k+1}$
$= F_{k+2} + F_{k+1} - 1 = F_{k+3} - 1$
（最後の等号はフィボナッチの漸化式 $F_{k+3} = F_{k+2} + F_{k+1}$ による。）
よって $n = k+1$ で成り立つ。 $\square$
$n$ 個の円（どの2つも異なる2点で交わり、どの3つも同一点で交わらない）は平面を最大 $n^2 - n + 2$ 領域に分割することを数学的帰納法で示せ。
[Step 1] $n = 1$：1つの円で内側・外側の $2$ 領域。$1-1+2 = 2$。成り立つ。
[Step 2] $n = k$ で $k^2-k+2$ 領域と仮定する。$k+1$ 番目の円を追加すると：
新しい円は既存の $k$ 個の円とそれぞれ $2$ 点で交わり、合計 $2k$ 個の交点を持つ。
$2k$ 個の交点で新しい円は $2k$ 個の弧に分割される。各弧が既存の $1$ 領域を $2$ つに分けるので、領域は $2k$ 個増加。
$(k^2 - k + 2) + 2k = k^2 + k + 2 = (k+1)^2 - (k+1) + 2$
よって $n = k+1$ でも成り立つ。 $\square$
すべての $2$ 以上の自然数 $n$ は素数の積として表せることを強い帰納法で証明せよ（素因数分解の存在）。
[Step 1] $n = 2$：$2$ は素数であり、$2$ 自身が素数の積（1つの積）。成り立つ。
[Step 2] $2$ 以上 $k$ 以下のすべての自然数で成り立つと仮定する。$k + 1$ を考える。
場合1：$k+1$ が素数のとき。$k+1$ 自身が素数の積。成り立つ。
場合2：$k+1$ が合成数のとき。$k+1 = ab$（$2 \leq a, b \leq k$）と書ける。
仮定より $a$ も $b$ も素数の積として表せる。よって $k+1 = ab$ も素数の積。成り立つ。 $\square$
$k+1$ が合成数のとき $k+1 = ab$ の $a, b$ は $k+1$ より小さいので仮定が使えます。通常の帰納法（$P(k) \Rightarrow P(k+1)$）では $P(k)$ しか使えず、$a, b$ について何も言えません。これが強い帰納法を使う典型的な理由です。