高校数学では、数学的帰納法を「$n = 1$ で成り立つことを確認し、$n = k$ で成り立つと仮定して $n = k+1$ でも成り立つことを示す」という手順として学びます。
この手順に従えば、すべての自然数 $n$ について命題が正しいと結論できる ── ではなぜ、この手順で「すべて」が言えるのでしょうか。
大学数学では、帰納法が正しい理由はペアノの公理に遡ります。
帰納法の原理は自然数を特徴づける公理の一つであり、これと同値な原理として整列原理（自然数の空でない部分集合には必ず最小元が存在する）があります。
この同値性を理解すると、高校の帰納法がなぜ正しいかが明確になるだけでなく、強い帰納法や超限帰納法など、より強力な証明手法の仕組みも見通せるようになります。
高校の数学Bでは、数学的帰納法を次の2ステップからなる証明法として学びます。
この2つが示されれば、すべての自然数 $n$ について $P(n)$ が成り立つと結論します。
典型的な例として、$1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ を数学的帰納法で証明する問題があります。
基底段階：$n = 1$ のとき、左辺 $= 1$、右辺 $= \dfrac{1 \cdot 2}{2} = 1$。成り立ちます。
帰納段階：$n = k$ で成り立つと仮定します。つまり $1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}$ とします。$n = k+1$ のとき、
$$1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$$
これは $n = k+1$ のときの右辺 $\dfrac{(k+1)(k+2)}{2}$ に一致します。
高校ではこの手順を繰り返し練習しますが、「なぜこの2ステップで"すべての自然数"が言えるのか」という問いには踏み込みません。 「ドミノ倒しのようなものだ」という比喩で説明されることが多いのですが、比喩は証明ではありません。 次のセクションでは、この「なぜ」に答えます。
大学数学では、数学的帰納法の正しさを「自然数とは何か」という問いから説明します。 自然数を公理的に定義するペアノの公理において、帰納法の原理そのものが公理の一つとして組み込まれています。 つまり、帰納法が正しい理由は「それが自然数の定義の一部だから」です。
この記事を読むと、以下のことがわかります。
ここからの構成は次の通りです。まずセクション3でペアノの公理を導入し、帰納法の原理が公理として位置づけられることを確認します。 次にセクション4で、帰納法の原理と整列原理が同値であることを証明します。 セクション5では、整列原理を使って強い帰納法を導出し、具体例で実際に使ってみます。
高校までは「自然数とは $1, 2, 3, \ldots$ のことだ」と直感的に理解しています。 しかし「$\ldots$」は厳密な定義ではありません。 19世紀末、イタリアの数学者ジュゼッペ・ペアノは、自然数を5つの条件（公理）で特徴づけました。
なぜ公理が必要なのでしょうか。数学では、あらゆる定理は出発点となる仮定（公理）から論理的に導かれます。 「$1, 2, 3, \ldots$」と書いただけでは、自然数がどんな性質を持つかを正確に述べたことになりません。 ペアノの公理は、自然数が満たすべき性質を過不足なく定めることで、帰納法を含むすべての議論の出発点を提供します。
以下では自然数の集合を $\mathbb{N}$、「次の数を与える操作」を $S$ と書きます。$S(n)$ は $n$ の後者（successor）と呼ばれ、直感的には $n + 1$ に対応するものです。
集合 $\mathbb{N}$ と、その元 $1 \in \mathbb{N}$ と、写像 $S : \mathbb{N} \to \mathbb{N}$ が以下の5条件を満たすとき、$\mathbb{N}$ を自然数の集合と呼びます。
公理1〜4は「自然数は $1$ から始まり、$S$ で一つずつ増えていく」ことを述べています。 公理5が帰納法の原理であり、「$1$ から $S$ で到達できない"余計な元"は自然数に含まれない」ことを保証します。
公理1と公理2は「出発点が存在し、次の数をいくらでも作れる」ことを述べています。 これだけでは $1, S(1), S(S(1)), \ldots$ つまり $1, 2, 3, \ldots$ という列ができますが、問題が2つ残ります。
問題1：ループしないか。 もし $S(3) = 1$ だとすると、$1 \to 2 \to 3 \to 1 \to 2 \to \cdots$ とループしてしまい、有限個の数しか作れません。公理3（$S(n) \neq 1$）がこれを防ぎます。
問題2：合流しないか。 もし $S(2) = S(4)$ だとすると、$2$ と $4$ の「先」が同じになり、自然数の列が分岐・合流する奇妙な構造になります。公理4（$S$ の単射性）がこれを防ぎます。
問題3：余計な元が混ざらないか。 公理1〜4だけでは、$1, 2, 3, \ldots$ の列に加えて、それとは独立な元（たとえば $a, S(a), S(S(a)), \ldots$ のような列）が $\mathbb{N}$ に含まれていても矛盾しません。公理5（帰納法の公理）は、そのような余計な元を排除します。
公理5を使って確認してみましょう。$A = \{1, 2, 3, \ldots\}$（$1$ から $S$ を繰り返し適用して作れるすべての元）とします。$1 \in A$ であり、$k \in A$ ならば $S(k) \in A$ です。公理5より $A = \mathbb{N}$ となり、$\mathbb{N}$ には $1$ から $S$ で到達できる元しか含まれません。
誤解：数学的帰納法は、他の定理や論理法則から導ける「証明テクニック」である。
正確：数学的帰納法の原理は、ペアノの公理の一つです。帰納法は自然数の定義に組み込まれた性質であり、他の定理から「導く」ものではありません。ただし、後で見るように、帰納法の公理と同値な原理（整列原理）は存在し、どちらを公理として採用しても同じ理論が得られます。
ここまでで、帰納法の原理がペアノの公理の一つであることを確認しました。 これが「帰納法はなぜ正しいか」に対する答えの一つです。帰納法は自然数の定義そのものに含まれているのです。 次のセクションでは、この帰納法の公理と密接に関連する整列原理を導入し、両者が同値であることを証明します。
セクション3で、帰納法の原理がペアノの公理の一つであることを見ました。 ここでは、帰納法の原理と同値な別の原理 ── 整列原理 ── を導入します。 「同値」とは、一方を仮定すれば他方が証明でき、逆も成り立つということです。 どちらを公理として採用しても、得られる自然数の理論は同じになります。
$\mathbb{N}$ の空でない部分集合 $A$（$A \neq \emptyset$, $A \subseteq \mathbb{N}$）には、必ず最小元が存在する。
つまり、ある $a_0 \in A$ が存在して、すべての $a \in A$ に対して $a_0 \leq a$ が成り立つ。
この性質を持つ順序を整列順序（well-ordering）と呼びます。 自然数は通常の大小関係に関して整列集合です。 一方、整数 $\mathbb{Z}$ は整列集合ではありません（たとえば $\mathbb{Z}$ 自身には最小元がありません）。
整列原理は直感的には当たり前に見えます。自然数の空でない集合が与えられたら、$1$ から順に調べていけば、いつかその集合の元に当たるはずです。 しかし「いつか当たるはず」は厳密な証明ではありません。以下で、帰納法の原理から整列原理を、整列原理から帰納法の原理を、それぞれ導出します。
目標：帰納法の原理を仮定して、「$\mathbb{N}$ の空でない部分集合 $A$ には最小元が存在する」ことを示します。
方針：$A$ に最小元がないと仮定して矛盾を導く（背理法）。具体的には、$A$ に最小元がないなら $A = \emptyset$ となることを帰納法で示します。
証明：$A$ を $\mathbb{N}$ の部分集合で、最小元を持たないものとします。$B = \mathbb{N} \setminus A$（$A$ の補集合）とおきます。$B = \mathbb{N}$ であることを帰納法で示します。
基底段階：$1 \in B$ でしょうか。もし $1 \in A$ ならば、$1$ は $\mathbb{N}$ の最小の元なので $A$ の最小元になります。これは「$A$ に最小元がない」という仮定に矛盾します。よって $1 \notin A$、すなわち $1 \in B$ です。
帰納段階：$1, 2, \ldots, k$ がすべて $B$ に属する（つまり $A$ に属さない）と仮定します。$k + 1 \in B$ でしょうか。もし $k + 1 \in A$ ならば、$1, 2, \ldots, k$ はすべて $A$ に属さないので、$k + 1$ は $A$ の中で最小です。これは仮定に矛盾します。よって $k + 1 \in B$ です。
帰納法の原理より $B = \mathbb{N}$、したがって $A = \emptyset$ です。対偶を取ると、$A \neq \emptyset$ ならば $A$ には最小元が存在します。
この証明の帰納段階で「$1, 2, \ldots, k$ がすべて $B$ に属する」と仮定していることに注意してください。 これは「$n = k$ で成り立つ」だけでなく「$n = 1, 2, \ldots, k$ のすべてで成り立つ」と仮定しており、実はセクション5で導入する強い帰納法の形になっています。 強い帰納法が通常の帰納法から導けることもセクション5で確認します。
目標：整列原理を仮定して、帰納法の原理「$1 \in A$ かつ $k \in A \Rightarrow k+1 \in A$ ならば $A = \mathbb{N}$」を示します。
方針：$A \neq \mathbb{N}$ と仮定して矛盾を導きます。
証明：$A$ が帰納法の条件 (i) $1 \in A$ と (ii) $k \in A \Rightarrow k+1 \in A$ を満たすとします。$A \neq \mathbb{N}$ と仮定すると、$C = \mathbb{N} \setminus A$ は空でない $\mathbb{N}$ の部分集合です。
整列原理より、$C$ には最小元 $c_0$ が存在します。条件 (i) より $1 \in A$ なので $1 \notin C$、つまり $c_0 \neq 1$ です。$c_0 \geq 2$ なので $c_0 - 1 \geq 1$ であり、$c_0 - 1 \in \mathbb{N}$ です。
$c_0$ は $C$ の最小元なので、$c_0 - 1 \notin C$、つまり $c_0 - 1 \in A$ です。条件 (ii) より $(c_0 - 1) + 1 = c_0 \in A$ となります。しかし $c_0 \in C = \mathbb{N} \setminus A$ なので矛盾です。
よって $A = \mathbb{N}$ です。
上の2つの証明により、帰納法の原理と整列原理は同値であることが示されました。どちらも「自然数には"最初の元"があり、そこから一つずつ数えて到達できない元は存在しない」という、自然数の本質的な性質を異なる角度から表現しています。
帰納法の原理は「下から積み上げる」視点（$1$ から始めて $S$ で進む）、整列原理は「上から降りる」視点（空でない集合には必ず"底"がある）と解釈できます。
ここまでで、帰納法の原理がペアノの公理の一つであること（セクション3）と、それが整列原理と同値であること（本セクション）を確認しました。 次のセクションでは、整列原理を使って強い帰納法を導出します。 強い帰納法は高校では扱いませんが、通常の帰納法では仮定が弱すぎて直接証明しにくい命題に有効です。
高校で学ぶ帰納法では、帰納段階で「$P(k)$ が成り立つ」という1つの仮定から $P(k+1)$ を導きます。 しかし、場面によっては「$P(1), P(2), \ldots, P(k)$ がすべて成り立つ」と仮定した方が証明しやすいことがあります。 この形の帰納法を強い帰納法（strong induction）または完全帰納法（complete induction）と呼びます。
命題 $P(n)$ について、以下の2条件が成り立つとする。
このとき、すべての自然数 $n$ に対して $P(n)$ が成り立つ。
通常の帰納法との違いは、帰納段階の仮定にあります。通常の帰納法では $P(k)$ のみを仮定しますが、強い帰納法では $P(1), P(2), \ldots, P(k)$ のすべてを仮定します。仮定が強い分、$P(k+1)$ を導きやすくなります。
強い帰納法が正しいことを、セクション4で導いた整列原理を使って証明します。
目標：強い帰納法の条件 (1), (2) を満たす命題 $P(n)$ が、すべての自然数 $n$ で成り立つことを示します。
方針：$P(n)$ が成り立たない $n$ が存在すると仮定し、整列原理を使って矛盾を導きます。
証明：$F = \{n \in \mathbb{N} \mid P(n)$ が偽$\}$ とおき、$F \neq \emptyset$ と仮定します。整列原理より $F$ には最小元 $m$ が存在します。
条件 (1) より $P(1)$ は真なので $1 \notin F$、つまり $m \geq 2$ です。$m$ は $F$ の最小元なので、$1, 2, \ldots, m-1$ はすべて $F$ に属しません。つまり $P(1), P(2), \ldots, P(m-1)$ はすべて真です。
条件 (2) で $k = m - 1$ とすると、「$P(1), \ldots, P(m-1)$ がすべて成り立つ」ならば「$P(m)$ が成り立つ」です。仮定より $P(1), \ldots, P(m-1)$ は真なので、$P(m)$ も真です。しかし $m \in F$ は「$P(m)$ が偽」を意味するので矛盾です。
よって $F = \emptyset$、すなわちすべての自然数 $n$ で $P(n)$ が成り立ちます。
逆に、強い帰納法から通常の帰納法が導けることも確認しておきます。通常の帰納法は、強い帰納法の仮定のうち $P(k)$ だけを使う特殊ケースです。つまり「$P(1), \ldots, P(k)$ がすべて成り立つ」と仮定しても $P(k)$ だけ使って $P(k+1)$ を導くなら、それは通常の帰納法にほかなりません。したがって、通常の帰納法と強い帰納法は同値です。
強い帰納法が威力を発揮する具体例を見てみましょう。命題 $P(n)$：「$n$ は素数であるか、または素数で割り切れる」を、$n \geq 2$ のすべての自然数について証明します。
基底段階：$n = 2$ は素数なので $P(2)$ は真です。
帰納段階：$P(2), P(3), \ldots, P(k)$ がすべて成り立つと仮定します。$P(k+1)$ を示します。
$k + 1$ が素数ならば、$P(k+1)$ は明らかに真です。$k + 1$ が素数でないならば、$k + 1 = ab$（$2 \leq a, b \leq k$）と書けます。ここで $a \leq k$ なので、帰納法の仮定より $P(a)$ が成り立ちます。つまり $a$ は素因数 $p$ を持ちます。$p$ は $a$ を割り切り、$a$ は $k+1$ を割り切るので、$p$ は $k+1$ も割り切ります。よって $P(k+1)$ は真です。
この証明では、$P(k)$ だけでなく $P(a)$（$a \leq k$）を使っている点が重要です。通常の帰納法では $P(k)$ しか仮定できないため、この形の証明は直接書けません。
強い帰納法をさらに一般化すると、自然数だけでなく任意の整列集合（空でない部分集合が必ず最小元を持つ順序集合）の上で帰納法が使えます。これを超限帰納法（transfinite induction）と呼びます。
超限帰納法は、自然数の集合を超えた「順序数」と呼ばれる対象を扱う集合論で用いられます。 セクション4で見た「帰納法と整列原理の同値性」という構造が、自然数に限らずより一般の整列集合でも成り立つことが、超限帰納法の正当性を支えています。
ここまでで、帰納法の理論的基盤（ペアノの公理、整列原理との同値性）と、その拡張である強い帰納法を見てきました。 次のセクションでは、これらの道具を応用して、帰納法で証明できる定理の具体例をいくつか取り上げます。
帰納法は等式や不等式の証明だけでなく、幅広い場面で使われます。ここでは、帰納法（とその変種）の応用例をいくつか見ていきます。
セクション5の具体例を発展させて、次の定理を証明します。
定理：$2$ 以上のすべての自然数は、素数の積として表すことができる（素因数分解の存在）。
目標：すべての自然数 $n \geq 2$ に対して、$n$ は1つ以上の素数の積として書けることを示します。
基底段階：$n = 2$ は素数であり、$2 = 2$ と（自明な）1つの素数の積として表されます。
帰納段階：$2, 3, \ldots, k$ のすべてが素数の積として表せると仮定します（強い帰納法の仮定）。$k + 1$ について考えます。
$k + 1$ が素数ならば、$k + 1$ はそれ自身1つの素数の積です。
$k + 1$ が合成数ならば、$k + 1 = ab$（$2 \leq a, b \leq k$）と書けます。帰納法の仮定より、$a$ と $b$ はそれぞれ素数の積として表せます。よって $k + 1 = ab$ も素数の積として表せます。
この定理は、素因数分解の存在を主張するものです。素因数分解の一意性（並べ方を除いて分解が一通りしかないこと）は、これとは別の定理であり、ユークリッドの互除法などを使った別の議論が必要です。 一意性については M-2-1 素因数分解の一意性 で詳しく扱っています。
高校の数学IIで学ぶ二項定理も、帰納法で証明できます。
定理（二項定理）：すべての自然数 $n$ と、任意の実数 $a, b$ に対して、
$$(a + b)^n = \sum_{r=0}^{n} \binom{n}{r} a^{n-r} b^r$$
基底段階：$n = 1$ のとき、左辺 $= a + b$、右辺 $= \binom{1}{0}a^1 b^0 + \binom{1}{1}a^0 b^1 = a + b$。一致します。
帰納段階：$n = k$ で成り立つと仮定します。
$$(a+b)^{k+1} = (a+b)(a+b)^k = (a+b)\sum_{r=0}^{k}\binom{k}{r}a^{k-r}b^r$$
右辺を展開すると、
$$= \sum_{r=0}^{k}\binom{k}{r}a^{k+1-r}b^r + \sum_{r=0}^{k}\binom{k}{r}a^{k-r}b^{r+1}$$
第2の和で $r$ を $r-1$ に置き換えると、
$$= \sum_{r=0}^{k}\binom{k}{r}a^{k+1-r}b^r + \sum_{r=1}^{k+1}\binom{k}{r-1}a^{k+1-r}b^r$$
$r = 0$ の項と $r = k+1$ の項を分離し、$1 \leq r \leq k$ の部分をまとめると、
$$= a^{k+1} + \sum_{r=1}^{k}\left[\binom{k}{r} + \binom{k}{r-1}\right]a^{k+1-r}b^r + b^{k+1}$$
パスカルの恒等式 $\binom{k}{r} + \binom{k}{r-1} = \binom{k+1}{r}$ を使うと、
$$= \binom{k+1}{0}a^{k+1} + \sum_{r=1}^{k}\binom{k+1}{r}a^{k+1-r}b^r + \binom{k+1}{k+1}b^{k+1} = \sum_{r=0}^{k+1}\binom{k+1}{r}a^{k+1-r}b^r$$
これは $n = k+1$ の場合の二項定理にほかなりません。
この証明では、帰納段階で $n = k$ の結果（$(a+b)^k$ の展開）を直接使って $(a+b)^{k+1}$ を導いています。帰納法の典型的なパターンです。
帰納法は強力な道具ですが、万能ではありません。帰納法が使いにくい、あるいは使えない典型的な場面を挙げておきます。
帰納法が使える場面と使えない場面を区別するには、「命題が自然数で添字付けされているか」「$P(k)$ と $P(k+1)$ の間に論理的な関係があるか」を確認するのが有効です。
Q1. ペアノの公理は5つあります。そのうち、帰納法の原理に対応するのは第何番目の公理ですか。また、その公理が果たす役割を一文で述べてください。
Q2. 整列原理とは何ですか。20字程度で述べてください。
Q3. 整数 $\mathbb{Z}$ の全体は整列集合ですか。理由とともに答えてください。
Q4. 強い帰納法と通常の帰納法の帰納段階の違いを説明してください。
ペアノの公理において、公理3（$S(n) \neq 1$）がなかったとします。このとき、$\mathbb{N} = \{1, 2, 3\}$、$S(1) = 2$、$S(2) = 3$、$S(3) = 1$ という集合と後者関数がペアノの残りの公理（公理1, 2, 4, 5）をすべて満たすかどうか、一つずつ確認してください。
公理1：$1 \in \{1,2,3\}$ なので満たします。
公理2：$S(1)=2$, $S(2)=3$, $S(3)=1$ で、すべて $\{1,2,3\}$ の元なので満たします。
公理4：$S$ は $1 \mapsto 2, 2 \mapsto 3, 3 \mapsto 1$ で単射なので満たします。
公理5：$A = \{1,2,3\}$ とすると $1 \in A$ かつ $k \in A \Rightarrow S(k) \in A$ なので $A = \mathbb{N}$ です。他の部分集合、たとえば $\{1,2\}$ は $S(2)=3 \notin \{1,2\}$ なので条件 (ii) を満たしません。公理5は満たします。
このように、公理3がないと有限の循環集合がペアノの公理を満たしてしまいます。公理3（$S(n) \neq 1$）は、自然数が有限でループする構造を排除するために不可欠です。
数学的帰納法を用いて、すべての自然数 $n$ に対して $1^2 + 2^2 + 3^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$ を証明してください。
基底段階：$n=1$ のとき、左辺 $= 1$、右辺 $= \dfrac{1 \cdot 2 \cdot 3}{6} = 1$。成り立ちます。
帰納段階：$n = k$ で成り立つと仮定します。$n = k+1$ のとき、
$$1^2 + 2^2 + \cdots + k^2 + (k+1)^2 = \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}$$
これは $n = k+1$ の場合の右辺 $\dfrac{(k+1)(k+2)(2(k+1)+1)}{6}$ に一致します。
整列原理を使って、次の命題を証明してください：「すべての自然数 $n$ に対して $2^n > n$ が成り立つ。」
（ヒント：$2^n \leq n$ となる自然数の集合を考え、その集合に最小元があると仮定して矛盾を導きます。）
$F = \{n \in \mathbb{N} \mid 2^n \leq n\}$ とおき、$F \neq \emptyset$ と仮定します。整列原理より $F$ には最小元 $m$ が存在します。
$m = 1$ のとき：$2^1 = 2 > 1$ なので $1 \notin F$。矛盾。よって $m \geq 2$。
$m \geq 2$ のとき：$m$ は $F$ の最小元なので $m - 1 \notin F$、つまり $2^{m-1} > m - 1$。両辺を2倍すると $2^m > 2(m-1) = 2m - 2$。$m \geq 2$ より $2m - 2 \geq m$。したがって $2^m > m$ となり $m \notin F$。矛盾。
よって $F = \emptyset$、つまりすべての自然数 $n$ に対して $2^n > n$ が成り立ちます。
この証明は、帰納法の代わりに整列原理を直接使うパターンです。セクション4で学んだように、帰納法と整列原理は同値なので、どちらを使っても同じ命題を証明できます。整列原理による証明は「反例の集合に最小元を取り、矛盾を導く」という定型的な構造を持つため、慣れると機械的に書けるようになります。
強い帰納法を使って、次の命題を証明してください：「すべての $2$ 以上の自然数 $n$ は、$n = 2^a \cdot m$（$a \geq 0$, $m$ は奇数）の形に表せる。」
基底段階：$n = 2$ のとき、$2 = 2^1 \cdot 1$（$a = 1$, $m = 1$ は奇数）。成り立ちます。
帰納段階：$2, 3, \ldots, k$ のすべてが $2^a \cdot m$（$m$ は奇数）の形に表せると仮定します。$k + 1$ について考えます。
$k + 1$ が奇数ならば、$k + 1 = 2^0 \cdot (k+1)$（$a = 0$）です。
$k + 1$ が偶数ならば、$k + 1 = 2 \cdot \dfrac{k+1}{2}$ と書けます。$\dfrac{k+1}{2}$ は $2 \leq \dfrac{k+1}{2} \leq k$ を満たす自然数なので（$k + 1 \geq 4$ の場合。$k + 1 = 2$ の場合は基底段階で処理済み）、帰納法の仮定より $\dfrac{k+1}{2} = 2^{a'} \cdot m'$（$m'$ は奇数）と表せます。
したがって $k + 1 = 2 \cdot 2^{a'} \cdot m' = 2^{a'+1} \cdot m'$ であり、$m'$ は奇数なので題意の形になります。
帰納段階で $\dfrac{k+1}{2} \leq k$ という $k+1$ より小さい自然数に関する仮定を使っている点が、強い帰納法の典型です。通常の帰納法では $P(k)$（$k$ に関する仮定）しか使えないため、$\dfrac{k+1}{2}$ に帰納法の仮定を適用できません。
次の「証明」は誤りを含んでいます。どこが間違っているかを指摘し、なぜこの誤りが生じるかを帰納法の構造に基づいて説明してください。
「定理」：すべての自然数 $n$ に対して、$n$ 頭の馬はすべて同じ色である。
「証明」：$P(n)$：「任意の $n$ 頭の馬の集合において、すべての馬は同じ色である」とする。
基底段階：$n = 1$ のとき、$1$ 頭の馬の集合では、馬は1頭だけなので「すべての馬は同じ色」は自明に成り立つ。
帰納段階：$P(k)$ が成り立つと仮定する。$k + 1$ 頭の馬 $h_1, h_2, \ldots, h_{k+1}$ を考える。$\{h_1, h_2, \ldots, h_k\}$ は $k$ 頭の集合なので、帰納法の仮定より同じ色である。同様に $\{h_2, h_3, \ldots, h_{k+1}\}$ も $k$ 頭の集合なので同じ色である。$h_2$ は両方の集合に含まれるので、$k + 1$ 頭すべてが同じ色である。
誤りは帰納段階の $k = 1$ の場合にあります。$k = 1$ のとき $k + 1 = 2$ 頭の馬 $h_1, h_2$ を考えます。$\{h_1\}$ と $\{h_2\}$ はそれぞれ1頭の集合なので $P(1)$ より各集合内の馬は同じ色ですが、2つの集合の共通部分は空です。つまり $h_2$ が両方の集合に含まれるという議論は $k \geq 2$ のときにしか成り立ちません。
$P(1) \Rightarrow P(2)$ の推論が成り立たないため、帰納法の鎖が $n = 1$ の段階で切れています。$P(2)$ が示されない以上、$P(3), P(4), \ldots$ も示されません。
この問題は「馬の色問題」として知られる有名な誤った帰納法の例です。帰納法の証明では、帰納段階がすべての $k \geq 1$ で成り立つことを確認する必要があります。特に $k$ が小さいとき（基底段階の直後）に推論が成り立たなくなるケースは見落としやすいので、帰納段階を書いたら必ず $k$ の最小の値（通常は $k = 1$）で議論が成り立つか確認する習慣をつけましょう。