Courtesy of Milind and 
http://www-courses.cs.uiuc.edu/~cs375/Problem_Sets/ps0/ps00s.pdf:

Can you prove that all horses are the same color?

Base case: 
Obviously, for any group with just one horse, all horses in the group
have the same color.

Inductive step: 

Assume that for any group with n-1 horses, all the  horses are the
same color. Now, consider a set of n horses. Remove one  horse from
the set, and you are left with n-1 horses. All of these are  obviously
the same color, by the induction hypothesis. Now remove one  of these
horses and add in the horse that you'd left out before. The  induction
hypothesis says that all _these_ horses must be the same  color. Since
there are some horses (n-2) that were in both sets, obviously all the
horses are the same color.

This, then, obviously breaks down for n = 2, as there are 0 horses
that  are in both sets, and it is the intersection being nonempty that
is  required to complete the proof. If you leave out the bit about 
"n - 2,"  it becomes a bit harder to spot the problem in the proof.