Now that we’ve seen how useful induction can be, I’d like to use it to establish a clear falsehood:

All horses are the same color.

The first hurdle to jump is figuring out how to make this an inductive argument. But that’s not too hard; I will translate the original claim into the following equivalent form: for every natural number n, every group consisting of n horses is monochromatic (i.e. they are all the same color).

Now we can get our induction off the ground. The case n = 1 is obvious: every group consisting of 1 horse is monochromatic. Next comes the induction hypothesis: we are allowed to assume the result is true for n, and our job is to prove it true for n + 1. So consider a group of n + 1 horses. How can we show that they are all the same color? Well, our inductive hypothesis tells us that every group of n horses is monochromatic. So all we have to do is remove one horse, call him Paul, from our group of n + 1 horses and consider the remaining group; call it G₁. There are n horses left in G₁, so by the inductive hypothesis they are all the same color. Now we have the problem that Paul is perhaps a different color than the rest. But this problem too can be overcome: simply remove a different horse from the original group. This leaves behind a new group of n horses which includes Paul; call it G₂. Again we apply our inductive hypothesis, this time to deduce that G₂ is monochromatic. But if Paul is the same color as all the horses in G₂, then Paul must be the same color as a horse in G₁, since every horse in G₂ except Paul is also in G₁. This then shows that Paul is the same color as every horse in G₁ (since G₁ is monochromatic), and so the original group of n + 1 horses is monochromatic. This completes the induction and thereby proves that all horses are the same color.

This is an excellent “proof ” to show to people who have just learned about induction for the first time. Even veterans of the technique can sometimes be perturbed by this argument if they haven’t seen it before in some form or another (it is quite common). What went wrong? In my experience, there are several ‘stages of doubt’ that one goes through in response to this seeming paradox, although the order may vary from person to person.

There is denial, something like, “Well, obviously the reformulation of the original claim isn’t equivalent, so induction can’t be applied.” But it is equivalent. Since there are (presumably) only finitely many horses in existence, one can simply take n to be the total number of horses to regain the first claim out of the second one. Alternatively, one can show that the second claim implies the first by contrapositive: if the first claim is false, so that not all horses are the same color, then we should be able to find two horses of different colors; this gives a non-monochromatic group (with n = 2), contradicting the second claim. (Here we don’t even rely on there being only finitely many horses).

Then there is a loss of faith in induction “Wait—you can’t assume the result is true for n! That’s circular!” But this assumption, the inductive hypothesis, is not the culprit. We have already discussed the logic underlying this assumption, and we have seen that induction is anything but circular.

Sometimes there is a stage of ridiculous doubt and wildly irrelevant claims: “Horses can’t be grouped! And what’s this about color? Horses have lots of colors, not just one!”

And perhaps, in the minds of those few whose adherence to the strictures of mathematics is unbreakable, there are even some fleeting moments of acceptance: “Maybe all horses are the same color. I mean, have you ever really looked?”

But in the end the fact remains that induction is not broken, yet horses do differ in color. Before reading on to the solution printed below, I suggest you let the problem torment you for a while.

A hint to what went wrong in the proof can be gleaned from solving the following simpler puzzle, which relies on the same misleading language to confuse the reader:

“How many pets do I have if all of them are dogs except two, all of them are cats except two, and all are parrots except two?”

This teaser comes from [2], where many others can be found and many hours can be spent on a joyful see-saw ride between befuddlement and insight.

The answer to this puzzle is that I have exactly three pets: one dog, one cat, and one parrot. The misleading use of the word ‘all’ to refer to only one thing is the source of the trouble here, as it is in the horse paradox. Let us return to the group G₂ and examine my assertion that “every horse in G₂ except Paul is also in G₁”. True enough, but quite vacuous in the case where n = 1 and the group G₂ consists of Paul alone. But this was the crucial claim that allowed me to conclude that Paul is the same color as the other horses in the original group of n + 1. When n = 1, the original group is a group of 2, and the logic fails entirely, since G₁ and G₂ have no horses in common.

This is the hole in the argument. It is not a problem with induction, but the inductive form of the argument does allow it to be easily concealed. The inductive step goes through for all values of n except 1. Every step in the reasoning—from 2 to 3, from 3 to 4, from 4 to 5—they all make sense, all except the very first step, from 1 to 2. And indeed, if we lived in a world where every group of two horses was monochromatic, then we would be living in a world where all horses are the same color. It would be a strange world, to be sure, but one thing is certain: mathematical induction would work just as well there as it does in our world.