Lemma: All horses are the same color. Proof (by induction):

Lemma: All horses are the same color.
Proof (by induction):
Case n=1: In a set with only one horse, it is obvious that all horses
in that set are the same color.
Case n=k: Suppose you have a set of k+1 horses. Pull one of these
horses out of the set, so that you have k horses. Suppose that all of
these horses are the same color. Now put back the horse that you took
out, and pull out a different one. Suppose that all of the k horses
now in the set are the same color. Then the set of k+1 horses are all
the same color. We have k true => k+1 true; therefore all horses are
the same color.