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.
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.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 3 images
