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.