What is wrong with this “proof” that all horses are the same color?
Let P(n) be the proposition that all the horses in a set of n horses are the same color. Basis Step: Clearly, P(1) is true. Inductive Step: Assume that P(k) is true, so that all the horses in any set of k horses are the same color. Consider any k + 1 horses; number these as horses 1, 2, 3, . . . , k, k + 1.
Now the first k of these horses all must have the same color, and the last k of these must also have the same color. Because the set of the first k horses and the set of the last k horses overlap, all k + 1 must be the same color. This shows that P(k + 1) is true and finishes the proof by induction.