Horse-Colour Paradox — Spot Where the Step From 1 to 2 Silently Breaks

Nothing teaches the discipline of induction like a proof that looks valid but secretly is not. The horse-colour paradox is the classical example: a beautifully structured induction argument that appears to prove, step by step, that all horses in the world are the same colour. Since that conclusion is obviously false, the proof must contain a flaw — and the flaw is almost invisible on a first reading.

The walk-through below helps you find the flaw. You step through the proof from n = 1 to n = 2, and the interactive diagram highlights exactly where the argument fails. If you have ever wondered how a careful-looking induction proof can be wrong, this is the cleanest possible example.

The "proof" (read slowly, resist the conclusion)

Claim. In any group of n horses, all horses are the same colour.

Base case (n = 1). A group of one horse contains only one horse, so all horses in the group are trivially the same colour. P(1) holds.

Inductive step. Assume P(k): in any group of k horses, all horses are the same colour. Show P(k+1): in any group of k + 1 horses, all are the same colour.

Take an arbitrary group of k + 1 horses, numbered H_1, H_2, \dots, H_{k+1}.

Consider the sub-group \{H_1, H_2, \dots, H_k\} — the first k horses. By P(k), all of these are the same colour. Call this colour A.
Consider the sub-group \{H_2, H_3, \dots, H_{k+1}\} — the last k horses. By P(k), all of these are the same colour. Call this colour B.
The horse H_2 (and also H_3, \dots, H_k) is in both sub-groups. So the colour A of the first sub-group equals the colour B of the second sub-group (both equal the colour of H_2).
Therefore H_1 (colour A) and H_{k+1} (colour B) have the same colour, and all k + 1 horses are the same colour.

By induction, P(n) holds for all n \geq 1. All horses are the same colour. \blacksquare

...which is obviously false. So where does the argument break?

The step-by-step walk-through

k = 1 (stepping k \u2192 k+1):

For each value of $k$, two sub-groups of size $k$ are shown: the first $k$ horses (green) and the last $k$ horses (orange), carved out of a group of $k + 1$. Their overlap (red) is what chains the two sub-groups together. At $k = 2, 3, \dots$ the overlap contains at least one horse \u2014 so the argument works. At $k = 1$, the overlap is empty \u2014 so the chain from "first sub-group" to "last sub-group" has no common horse and the colour equality cannot be inferred.

Where the argument actually fails

The inductive step in the bogus proof assumes that the two sub-groups \{H_1, \dots, H_k\} and \{H_2, \dots, H_{k+1}\} overlap — that they share at least one horse, through which the colour of the first sub-group is linked to the colour of the second.

Let us count the overlap precisely. The two sub-groups share the horses \{H_2, H_3, \dots, H_k\} — that is, k - 1 horses.

If k \geq 2, the overlap has at least one horse. The argument works for k = 2 \to k = 3, for k = 3 \to k = 4, and onward.
If k = 1, the overlap has zero horses. The two sub-groups are \{H_1\} and \{H_2\} — completely disjoint. There is no shared horse, so there is no reason the colour of H_1 should equal the colour of H_2. The chain breaks.

This is exactly the "missing inductive step" pattern from the domino-chain picture. The chain is correctly constructed for k \geq 2, but the step from k = 1 to k = 2 — the very first step beyond the base case — is where the argument silently fails. The proof established P(1) directly, but the inductive step cannot extend P(1) to P(2). And without P(2), nothing beyond can be established, because each higher step depends on the previous one.

Why "the step works for large k" does not save the proof: induction requires the step P(k) \Rightarrow P(k+1) to hold for every k \geq (base case). If the step fails at even one k, the chain reaches exactly up to that k and no further. Here, the step fails at k = 1, so the proof establishes P(1) (directly) and nothing else. Every P(n) for n \geq 2 is unsupported.

What the paradox teaches

Three lessons, each valuable when you write your own induction proofs:

The base case is not the weak link here; the inductive step is. Students often over-focus on the base case and under-examine the inductive step. In this paradox, the base case P(1) is perfectly valid. The trouble is entirely in the inductive argument.
An inductive step must work for every k above the base case, not just "large" k. The intuition "it clearly works when k is big" is a siren song. Check the smallest k you are stepping from — that is usually where the structural assumption breaks.
Look for hidden assumptions about size or configuration. The horse-colour proof secretly assumed |overlap| \geq 1. That assumption is true for k \geq 2 but false for k = 1. Any induction that relies on "this sub-structure is non-empty" or "this configuration is possible" should be audited for whether the assumption holds at the smallest relevant k.

The fix for the horse-colour "proof" is straightforward: you would need to verify P(2) directly as part of the base case, strengthening the foundation to cover the gap. Of course, P(2) — "any two horses are the same colour" — is false, so you cannot verify it. That is the honest diagnosis: the statement itself is not true, and the induction proof's failure at k = 1 \to 2 is the mathematics refusing to lie.

Four more "almost-induction" bugs to watch for

The horse-colour flaw is one species of a broader family:

The inductive step divides by k - 1 (or some expression that is zero at small k). Works for k \geq 2, fails at k = 1.
The inductive step assumes a specific configuration (two overlapping sub-groups, a tree with at least two leaves, a partition into two parts). Check that the configuration actually exists at small k.
The inductive step uses P(k) and P(k-1). This is strong induction in disguise and needs two base cases — you cannot just check P(1).
The statement is quantified over n \geq 0, but the inductive step assumes n \geq 1. Set your base case where the inductive step actually starts working.

Each of these shows up in real homework and real competition problems. The horse-colour paradox is the template — once you see the flaw there, you start seeing its cousins everywhere.

The one-line takeaway

When an induction proof looks airtight but the conclusion is obviously false, the flaw is almost always in the smallest inductive step. The horse-colour paradox fails at k = 1 \to 2 because the two sub-groups share no horse when k = 1. Always check the inductive step at the smallest k where it is claimed to work.