Thank you for visiting this site. This article covers the “All Horses Are the Same Color” paradox.
Using a proof technique called mathematical induction, one can apparently “prove” that every horse in the world is the same color. Of course, in reality that is impossible. So where exactly is the error in this “proof”?
The False Proof
Mathematical induction proceeds in two steps.
Base case: Show the statement holds for n = 1.
Inductive step: Assuming it holds for n = k, show it also holds for n = k + 1.
If both steps are established, the statement holds for all natural numbers — like a chain of falling dominoes.
Let’s try to prove: “In any set of n horses, all horses are the same color.”
Base case (n = 1): In a set of only one horse, all horses in the set (just the one) are trivially the same color. ✓
Inductive step: Assume that in any set of k horses, all are the same color.
Consider k + 1 horses: Horse 1, Horse 2, …, Horse k, Horse k+1.
The first k horses (1 through k) are all the same color by the inductive hypothesis.
The last k horses (2 through k+1) are also all the same color by the inductive hypothesis.
These two groups overlap in the horses numbered 2 through k. Therefore: color of first group = color of overlap = color of last group, showing that all k+1 horses are the same color.
By induction, the statement holds for all natural numbers n — so all horses are the same color.
…Or does it?
The Flaw
The error in this proof lies in the transition from n = 1 to n = 2.
Consider the case k = 1, so k + 1 = 2 — two horses, Horse 1 and Horse 2.
Following the inductive step’s logic:
- The first k horses (just Horse 1) are all the same color. Yes — one horse.
- The last k horses (just Horse 2) are all the same color. Yes — one horse.
But the “overlap” of the two groups is… empty.
The group containing only Horse 1 and the group containing only Horse 2 share no horse in common. The argument that “both groups share the same color via the overlap” therefore does not hold.
The inductive step is only valid for k ≥ 2. It breaks down at k = 1 (the step from n = 1 to n = 2), the very first domino fails to fall, and the induction collapses entirely.
Why This Paradox Is Educational
This paradox is frequently used in mathematics education precisely to emphasize the importance of verifying that the inductive step holds for all k, including the transition from the base case.
Induction is a powerful proof technique, but if the inductive step’s logic does not connect directly to the base case, a false proof can be constructed.
The paradox teaches students to ask: “Have I really verified that the inductive step holds for every k — especially the very first step?”
Summary
This article covered the “All Horses Are the Same Color” paradox.
The fact that a seemingly airtight proof conceals a subtle flaw in just one step underscores the importance of rigor in mathematics.
To return to the full list of paradoxes, follow the link below.
Thank you for reading. We hope to see you in the next article.
