What is the flaw in this induction proof?

Question

Explain the flaw in the following induction argument which shows all of Lucas’ toys are the same colour.

Proof: We will show by induction that: for every integer $n\ge1$, in any group of $n$ of Lucas’ toys, all the toys in this group are the same colour.

Basis: If Lucas had only one toy, then clearly all these toys are one colour, so the result holds for $n=1$.

Induction Hypothesis: Suppose for a fixed but arbitrary integer $k \ge 1$, in any group of $k$ of Lucas’ toys, all the toys in this group are the same colour.

Induction Step: Let $n = k + 1$. Take any fixed but arbitrary group of $k + 1$ of Lucas’ toys. Pick out an arbitrary toy (Toy A) from this group. Then all the remaining $k$ toys in the group are the same colour, by the induction hypothesis. Adding this toy back into the group and removing another toy (Toy B), we get a group of $k$ toys which contain Toy A. By the induction hypothesis, these $k$ toys are all the same colour. Thus all the toys in the group must be the same colour. Since the group chosen was arbitrary, in any group of $k + 1$ of Lucas’ toys, all the toys in this group are the same colour.

Conclusion: By the PMI, for all integers $n \ge 1$ any group of $n$ of Lucas’ toys are all the same colour. Therefore, since Lucas has a finite number of toys, all of Lucas’ toys are the same colour.

Answer 1

If you step back, one way to typify the issue is that the base case is faulty. We need to start with a base case such that the logic of the induction step holds when our base case does.

Suppose we try to apply the logic when we have $n=2$ toys, assuming that we have proven the base case for one toy. The inductive step implicitly relies on the fact that when we split it up into two groups of $k=1$ toys, there will be some mutual element shared within the group and hence, by transitivity, all toys would be of the same color.

However, when $n=2$, we don't have that mutual element, and hence the inductive step fails. To fix this proof, one would need to either change the inductive step to work for $k=1$ or prove the base case when $n=2$, of which both are clearl impossible since the result is absurd.

Answer 2

The statement of your inductive hypothesis is incorrect. As written, it assumes what you want to prove. (I.e. that all subsets of the set of toys have the same color.) The correct statement of your inductive hypothesis is "There exists a set of $k$ toys all of the same color."

This inductive hypothesis is not strong enough to show that there is a set of $k+1$ toys all of the same color, which is the correct inadequacy for this argument to have.

A way to see that this is correct is that the base case only supports the existence of one element sets for each of which all of a set's elements are the same color. It makes no promise that any two sets have the same color, and it is correct not to do so.