Comment on the following.
Theorem: All horses have the same color.
Proof by induction: Let P(n) be the statement "in any group of n horses, all horses have the same color".
Clearly, P(0) is true because if no horse is present, the question of color does not arise.
(Also, just as clearly, P(1) is true.)
So, suppose P(n) is true and try to show P(n+1). That means, we are given n+1 horses of names (say) H_1,...,H_(n+1) and we need to show they all have the same color.
If we forget for a moment the last one, we only have H_1,...,H_n and that is a group of just n horses. Since we assume P(n) to be true, these n horses all have the same color, call it C_1.
Now if instead we forget the first horse and just look at H_2,...,H_(n+1), then this is again a group of n horses. By the inductive hypothesis again, these n horses share the same color, say C_2.
Looking at the horses H_2,...,H_n which appear in both groups, it becomes evident that the colors C_1 and C_2 must actually be the same. It follows that all n+1 horses have the same color, namely color C_1=C_2. So, P(n+1) is true since we have shown that if P(n) is true then any group of n horses is of uniform color. $ \Box $
