###
Proof(?) that all horses are the same color

To prove: Any n horses, n>=1, are all the same color.
__Base case (n=1):__ Any horse is the same color as itself.

__Inductive step:__ If any r horses, 1<=r<=k, are all the same
color, then any k+1 horses are all the same color.

__Proof:__ Divide your k+1 horses into two non-empty groups. One group will have
x horses, and the other group will have (k+1)-x horses. Both x and
(k+1)-x are less than k+1, so by the inductive hypothesis each group
of horses is all the same color. Now choose one horse from the first
group and one horse from the second group. Again, by the inductive
hypothesis these two horses must be the same color, so all of the horses
must be the same color.