Why is "All horses have the same color" considered a false proof by induction?

Question

Upon reading of All horses have the same color "paradox", I began to wonder a couple of things.

First of all, to me the inductive step seems flawed. Just because I have $n$ white horses, does not mean that the $n+1$ will be white, too.

The only explanation to make the inductive step work seems to me that the actual statement we are assuming as base case it's not "there are at least $n$ horses of the same color", but rather "$P(n)$ = any grouping of $n$ horses is such all the horses in that grouping have the same color".

Now this makes the inductive step works, but it's completely useless, as $P(2)$ already implies that all the horses have the same color.

And of course the base case $P(2)$ is not true because it's equivalent to our problem. Setting to prove $P(2)$ is the same as proving that all horses have the same color.

So I can't understand why this has been considered a "false" proof by induction; either the inductive step does not work or it's completely useless.

The wikipedia page linked before explains the problem as

The problem in the argument is the assumption that because each of these two sets contains only one color of horses, the original set also contained only one color of horses. Because there are no common elements (horses) in the two sets, it is unknown whether the two horses share the same color.

Which does not make any sense to me.. It's like looking at the finger instead that at the moon.

Is there something wrong with my understanding of induction?

Edit

Admittedly, the base case is $P(1)$ and not $P(2)$. But the point holds;the only implication we need is $P(1) \implies P(2)$. All the subsequent implications are useless; a proof of this type is seldom called a proof by "induction". Otherwise all proofs are by induction! :)

What is even the point of establishing what $P(n)$ is? Just prove $P(2)$ and use as known fact $P(1)$ as you would do with any other known fact.

Edit 2

Since there has been some confusion about what I asked, I'll explain my thought process:

1) Begin reading the proof. Imagine that the statement is "P(n) = at least n horses have the same color", and if by induction on $n$ this hold for every $n$, then QED.

2) Realize the inductive step does not work

3) Understand that the proposition to be proved has been (silently) changed and now it's "P(n) = any grouping of $n$ horses is such all the horses in that grouping have the same color"."

4) Realize that $P(2)$ is what we want to prove.

5) Wonder why on earth we are trying to show $P(n)$ for $n > 2$. Induction proof usually works because the final statement to be proved come from the fact that it works for all $n$. Here $n=2$ suffice, so it is really odd.

6) Starting to think I've missed something here. But hey, it's a false proof, let's see what was wrong.

7) Turns out that the outline of the proof is fine but here's the catch: of all the implications $P(1) \implies P(2)$ is not valid hence the whole $P(n)$ cannot be valid.

8) Thinking (again) that this seems weird. Wonder if I've missed something .

By extended discussion it turns out that my understanding of induction was right. This lead me to believe that is is a bad example because it "seems" like a proof by induction but really some essential elements are not present. It's not that is wrong (apart from the failed implication), is that it gives a very bad idea of what a proof by induction is

Answer 1

The flaw lies in the sentence "the first horse in the group is of the same color as the horses in the middle, who in turn are of the same color as the last horse".

When $n=2$, this does not apply as there are no horses "in the middle", hence the "first" and "last" horses needn't be of the same color.

So $P(1)$ holds, and $P(n)$ does imply $P(n+1)$, but provided $n>2$: this suffices to ruin the argument.

Answer 2

Yes, proving $P(2)$ is good enough and you don't really need induction. The trouble is that $P(2)$ is false. The induction argument is there to obfuscate this fact by referring to a generic $n$ and hoping the reader doesn't notice that the general argument fails for $n=2$. That's why it's a false proof by induction.

Answer 3

It is very common that false proofs by induction involve a faulty base case, so a way to unravel the argument is to use the base case on the inductive step and see if the argument makes sense for that case.

First, exclude the last horse and look only at the first n horses; all these are the same color since n horses always are the same color. Likewise, exclude the first horse and look only at the last n horses. These too, must also be of the same color. Therefore, the first horse in the group is of the same color as the horses in the middle, who in turn are of the same color as the last horse. Hence the first horse, middle horses, and last horse are all of the same color, and we have proven that:

So the base case is $n=1$, and $n+1 = 2$.

It is true that the first horse has the same color as the first and the second horse has the same color as the second. But the problem is that when the argument refers to the "horses in the middle," there are no such horses for $n=2$. You just have the first horse and the last horse. This is where the argument fails.

Answer 4

Isn't the whole point of induction that if induction is true then $P(m) \implies P(n)$ for $n \geq m$? To formally use $P(2)$ and get $P(n)$ you would have to set up the induction, and it sound like you are assuming a statement about transitivity that you would prove with induction (albeit a fairly easy induction).

You seem to think that this is a bad or faulty example of induction because $P(2) \implies P(n)$ so proving $P(2)$ is sufficient, but think if $P(2) \not\implies P(n)$ then this would be an awful case of induction because it wouldn't even be induction. In fact in some sense this is a "classic" case of induction from the fact the truth value of $P(n)$ actually depends on on the previous cases, so you are building up from the previous cases to get the next case, so if $P(2)$ is your base case all future cases should be built from $P(2)$.