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?”
Where exactly the induction breaks
Follow the flaw a little more carefully. The weak point of the argument sits in exactly one place: the move from one horse to two.
The proof, group size by group size
| Transition | Overlap between the two groups | Does the argument work? |
|---|---|---|
| 1 → 2 | no horses in common | no |
| 2 → 3 | one horse in common | yes |
| 3 → 4 | two horses in common | yes |
| n → n+1 (n at least 2) | n−1 horses in common | yes |
The proof forms “the group with the first horse removed” and “the group with the last horse removed” and uses their overlap as a bridge.
With only two horses, though, the first group is just horse two and the second is just horse one. They share no horse at all, so the grounds for tying the colours together vanish.
The interesting part is that from three horses upward the argument is entirely sound. The claim “if any two horses are the same colour, then any number of them are” genuinely holds. Only the first rung is broken; the chain above it is fine.
In short, the false proof has the structure of a building whose foundation is a millimetre out — and everything above it comes down.
Other famous false proofs
Plenty of other proofs look right and are not.
| False proof | The claim | The error planted in it |
|---|---|---|
| A proof that 1 = 2 | all numbers are equal | it divides by zero partway through |
| Every triangle is isosceles | two sides of any triangle are equal | it ignores the case where the construction lines meet outside the figure |
| Rearranging an infinite series | the sum is both 0 and 1 | it reorders a conditionally convergent series |
| All horses are the same colour | every horse shares a colour | the base case does not connect to the next rung |
What they share is that the error is confined to one spot and everything else is perfectly correct. Nothing feels wrong when you take in the whole, which is exactly what makes the flaw hard to locate.
A checklist for using induction
The practical cautions this paradox yields:
- Check the starting point. Do not stop at showing that n = 1 works
- Actually take the first step. Verify the move from 1 to 2 concretely, not in general terms
- Count the conditions you used. Look for an unstated assumption such as “we need at least n−1 of them”
- Try small numbers. Check by hand that the conclusion really holds around 2 and 3
The second is the one that pays. An expression written for general n can look correct and still fall apart when you put a small value in.
This is not confined to mathematical proofs. A procedure written as a general rule breaking at the edge cases is an everyday occurrence in software design; a bug that only fires when the array holds zero or one element has exactly this shape.
Who thought of it
The false proof is generally credited to the Hungarian mathematician George Pólya, who popularised it.
Pólya wrote about how mathematical reasoning proceeds for a general readership, in books such as his 1954 work on induction and analogy in mathematics. What he valued was not memorising correct proofs but the ability to spot for yourself where an argument breaks.
The horses are presented as teaching material of that kind. Because the conclusion is obviously false, the reader is forced to go hunting for the hole — and in the hunting, learns in the body how much the base case of an induction matters.
The original version, by some accounts, was not about horses but about “all women having the same colour hair.” The details vary with the telling; the structure is the same.
Telling it apart from a correct proof
What the false proof teaches is that the two halves of an induction do different jobs.
- The base case shows that the starting point holds. You confirm this is true
- The inductive step shows that if n holds then n+1 holds. This is what builds the chain
Most people put their attention on proving the inductive step and wave the base case through as “obviously true.”
What actually tends to break, though, is the joint between the base case and the inductive step. The base case can be correct in itself while the inductive argument cannot start from it.
The horses are precisely that. It is true that one horse is the same colour as itself, and the argument for three or more is sound. And the whole still fails. Both halves can be right and still not connect.
When reading a proof by induction, it is worth checking concretely, once, whether the inductive argument can really be applied from the rung immediately above the base case.
Reading a proof, the eye goes to the inductive step. I make a point of doubting the starting point first — that is usually the side that breaks.
Related paradoxes of induction
Related paradoxes about the pitfalls of reasoning from what has been observed so far.
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.
Also popular with readers
📚 Series: The World's Paradoxes (76/81)
