What is wrong with this "proof" that all horses are the

Chapter 5, Problem 49E

(choose chapter or problem)

Problem 49E

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(l) 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.