Michael Sipser Edition 3 Exercise 0 Question 12 (Page No. 27)

Question

Find the error in the following proof that all horses are the same color.
CLAIM: In any set of h horses, all horses are the same color.
PROOF: By induction on $h.$
Basis: For $h = 1.$ In any set containing just one horse, all horses clearly are the
same color.

Induction step: For $k\geq 1,$ assume that the claim is true for $h = k$ and prove that it is true for $h = k + 1.$ Take any set $H$ of $k +1$ horses. We show that all the horses in this set are the same color. Remove one horse from this set to obtain the set $H_{1}$ with just $k$ horses. By the induction hypothesis, all the horses in $H_{1}$ are the same color. Now replace the removed horse and remove a different one to obtain the set $H_{2}.$ By the same argument, all the horses in $H_{2}$ are the same color. Therefore, all the horses in $H$ must be the same color, and the proof is complete.

Answer 1

The proof seems to be fine at first glance.

Let's take k=2 and try to prove the above result for k=3 using induction hypothesis(IH).

IH says any set of two horses have the same color. i.e say, {H1, H2} are of same color.

Now replace H1 by H3. Again, using IH, {H2, H3} are of the same color as it is a set of two horses.

so above results says- {H1, H2} are of same color and {H2, H3} are of same color which implies {H1, H2, H3} are of the same color as H2 is common in both the sets.

So we have successfully proved for k=3. and you can use a similar argument for k=4,5,6...... so on.

Base case shows that the proof is true for k=1. We proved above for k=3,4,5..... Now the only thing remaining is to show that proof works for k=2.

The flaw here is for the case k=2,

Using IH, set of one horse say {H1} has the same color.which is trivial as the set contain only one horse.

 Similarly, set {H2} has all the horses of the same color. again trivial.Only one horse in a set.

Does it mean that set {H1, H2} are of the same color?? NO!!!! Say H1 is of green color and H2 is of blue. (Though I haven't seen green or blue horses anywhere yet).

Clearly {H1,H2} DO NOT have same color. So, we fail to prove the case for k=2, Which was the error.