Fallacious proof/all horses are the same color

All horses are the same color

We shall prove that all horses are the same color by induction on the number of horses.

First we shall show our base case, that all horses in a group of 1 horse have the same color, to be true. Of course, there's only 1 horse in the group so certainly our base case holds.

Now assume that all the horses in any group of $k$ horses are the same color. This is our inductive assumption.

Using our inductive assumption, we will now show that all horses in a group of $k+1$ horses have the same color. Number the horses 1 through $k+1$. Horses 1 through $k$ must be the same color as must horses 2 through $k+1$. It follows that all of the horses are the same color.

Explanation

Our base case is not the appropriate base case: if one could show that every pair of horses has the same color (the result for $n = 2$), the fact that all horses have the same color would follow. Unfortunately, the case $n = 2$ does not follow from the case $n = 1$. The first horse is the same color as itself, and so is the second horse, but there is no overlap and so we cannot deduce that the two horses are the same color.

Back to main article

Invalid username
Login to AoPS