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 
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 
horses have the same color. Number the horses 1 through . Horses 1 through must be the same color as must horses 2 through . 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 
), the fact that all horses have the same color would follow. Unfortunately, the case does not follow from the case 
. 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.
