Why Does the Horse-Colour Paradox Break the Rules — the Induction Step Looks Fine?

The horse-colour paradox is the most famous fake induction proof. It claims to prove that any finite group of horses contains only horses of the same colour. The base case looks fine — one horse has the same colour as itself. The inductive step looks fine — you pull a horse out, swap it with another, and everything lines up. And the conclusion is absurd — obviously horses come in many colours. So the logic must break somewhere, but where?

The answer is beautiful and important: the inductive step is not uniformly valid for every k. It silently assumes k \geq 2, and fails exactly at k = 1 — the one rung you cannot afford to lose.

The argument, stated carefully

Claim. For every positive integer n, any set of n horses consists of horses of the same colour.

Base case (n = 1). A single horse has the same colour as itself. Trivially true.

"Inductive step." Assume the claim for n = k: any set of k horses is monochromatic. Let H = \{h_1, h_2, \dots, h_{k+1}\} be any set of k+1 horses. Consider two sub-sets:

A = \{h_1, h_2, \dots, h_k\} (the first k horses) — monochromatic by hypothesis.
B = \{h_2, h_3, \dots, h_{k+1}\} (the last k horses) — also monochromatic by hypothesis.

Now A and B share the horses h_2, \dots, h_k. Since every horse in A is the colour of (say) h_2, and every horse in B is also the colour of h_2, all k+1 horses share the colour of h_2. Done.

Conclusion. All horses, in any finite group, share a colour. This is clearly false, so something in the argument is wrong.

Where it actually breaks

Look at the sub-sets A and B when k = 1. Then k + 1 = 2, so H = \{h_1, h_2\}. The two sub-sets become:

A = \{h_1\} (the first 1 horse).
B = \{h_2\} (the last 1 horse).

Now A and B have no overlap — they share zero horses. The entire argument hinged on picking a shared horse h_2 and saying "everything in A matches h_2, and everything in B matches h_2." With empty overlap, there is no shared horse to bridge the two sides. h_1 and h_2 can each be monochromatic (vacuously — single horses always are) without sharing a colour.

The inductive step fails precisely when k = 1, which is the only rung where it actually needs to work.

Why the step is valid for k \geq 2: when k \geq 2, the sub-sets A and B share at least one horse (the horses at positions 2 through k, which is a non-empty range). That shared horse anchors the colour claim on both sides. For k = 1, the "shared range" is positions 2 through 1, which is empty. The bridging horse disappears, and the argument silently ceases to make sense.

The lesson: the inductive step must hold for every k starting from the base

An inductive step of the form "P(k) \Rightarrow P(k+1)" must be a valid implication for every k \geq 1 (or wherever the base case starts). It is not enough for the argument to look fine in the abstract. You have to check that the specific operations in the step — the picking, swapping, overlapping — are meaningful at the first value of k the step is supposed to cover.

The horse proof is a cautionary tale about trusting symbolic manipulation. The statement "A \cap B contains horses h_2, \dots, h_k" is technically true for all k \geq 2, but becomes vacuous when k = 1. The step "pick any horse from A \cap B" silently assumes A \cap B is non-empty — a hidden precondition the abstract argument never surfaced.

A test that catches the bug

Before you believe any inductive proof, perform this diagnostic: plug in k = (the smallest value the step should handle) and execute the step by hand.

For the horse argument, you plug in k = 1 and ask: "Given a monochromatic set of 1 horse, prove that any set of 2 horses is monochromatic." Try it. You have \{h_1, h_2\}. You invoke the hypothesis on \{h_1\} and on \{h_2\} — both monochromatic (trivially). Now you need to conclude they share a colour. You cannot. No argument exists at this rung. The step is broken, and you have found the bug by making it concrete.

A correct version of a similar argument

It is instructive to see what a valid version of the "overlap trick" looks like. Here is a real theorem that uses the same structural idea:

Claim. Every set of n \geq 2 points in the plane, no three collinear, with all pairwise distances equal, has at most 3 points.

You can prove this by a careful case analysis — not by induction, because there is no generic overlap trick that works at n = 2. In fact, for any overlap-based induction, you need the sub-sets to share at least one element, which demands k \geq 2 in the overlap scheme. Problems whose inductive structure requires overlap should be treated with suspicion at the low end.

A deeper moral

The horse proof has an important lesson beyond horses. The inductive step is a universally-quantified statement: for every k, the implication holds. If the step works for k \geq 2 but fails at k = 1, you have proved a chain that reaches from n = 2 upward — but it never connects back to the base case P(1). The chain is dangling, and the conclusion about "all n" is unearned.

There is a correct way to express what the horse argument actually proves, if you salvage what you have:

P(1) is true (one horse is monochromatic, trivially).
For k \geq 2, P(k) \Rightarrow P(k+1) is true.

This is not enough to prove P(n) for all n, because the chain from P(1) to P(2) is missing. To bridge it, you would need to separately prove P(2): "any two horses are the same colour." And that, of course, is false — which is why the whole argument collapses.

The takeaway for your own proofs

Whenever you write an inductive step, test it at the smallest value of k your base case hands you. If the step uses language like "pick any element of the overlap," "consider the middle term," or "remove one and look at the rest," make sure those operations are meaningful when k is small. A step that implicitly assumes k \geq 2 needs either a second base case for n = 2, or a revision of the argument to handle the edge.

The horse paradox is not a paradox at all — it is a proof with a bug, dressed up to look airtight. Finding the bug is the exercise, and the technique you use to find it is the same technique you should apply to your own inductive arguments.