What is wrong with the following “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. Clearly, P(1) is true. Now assume that P(n) is true, so that all the horses in any set of n horses are the same color. Consider any n + 1 horses; number these as horses 1, 2, 3, . . . , n, n + 1. Now the first n of these horses all must have the same color, and the last n of these must also have the same color. Since the set of the first n horses and the set of the last n horses overlap, all n + 1 must be the same color. This shows that P(n + 1) is true and finishes the proof by induction.
This proof is obviously wrong because I can easily prove that this is not the case by counter example. However, I am not 100% sure what the problem is with this proof. I was wondering if someone could maybe give me a hint, without an answer as to why its false.
My thoughts thus far is that unlike when you are proving things with math, there is no link between the number "n" which you are assigning a horse and its color. Due to the fact that having one horse being black, and the next one is, has nothing do do that the one after it is.
However, now that I have read it a second time I am thinking that maybe it is the fact that we can only assume that n-1 horses are of the same color, and that there is no way to prove that because the first n-1 horses are of one color the last one is. So, really what I am thinking is that the problem with this proof is that the assumption is incorrect, because we can only assume the first n-1 horses are the same color by the principals of mathematical induction. Do you think either of these is right? if not please give me a hint.