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

Problem     Prove that all horses (n) are the same color with induction.

Base Case   Obviously, for any group with just one horse (n=1), all horses 
            in the group have the same color.

Inductive   Assume that for any group with k-1 horses, all the horses are the
Hypothesis  same color.

Inductive   Consider a set of k horses.
Step        Remove one horse, which gives you k-1 horses (set H1).
            By the IH, we have a group that is all the same color now.
            
            Replace the horse you removed and take a different one.
            This set (H2) now also has k-1 horses of the same color.

	    Since the horses in H1 have the same color and some of those
            horses are in H2, and the H2-horses have the same color,
            H1 and H2 all have the same color.

            Wrong...why? When k=2, we have a problem.

	    H1 has one horse and H2 has one horse. We don't have a third
            horse to share in common. Since each horse might have its
            own color, we cannot conclude the general idea that all horses
            have the same color.