Chapter 9.5, Problem 35E

Solution

Where the proof goes wrong.

It has been explained where the proof went wrong.

Given:

A proof by mathematical induction that any gathering of $n$ persons must all have the same blood type.

(Anchor) If there is $1$ person in the gathering, everyone in the gathering obviously has the same blood type.

(Inductive hypothesis) Assume that any gathering of $k$ persons must all have the same blood type.

(Inductive step) Suppose $k+1$ persons are gathered. Send one of them out of the room. The remaining $k$ persons must all have the same blood type (by the inductive hypothesis). Now bring the first person back and send someone else out of the room. You get another gathering of $k$ persons, all of whom must have the same blood type. Therefore, all $k+1$ persons must have the same blood type, and we are done by mathematical induction.

Concept used:

In mathematical induction, there must be a connection between the base case and the inductive hypothesis. In other words, the simplest version of the inductive hypothesis must denote the base case.

Calculation:

In the given proof, more specifically, in the inductive step, the conclusion that all $k+1$ persons must have the same blood type is depended on the fact that the first person to be sent out of the room and the second person to be sent out of the room must have the same blood type based on the fact that when either of them is sent out of the room, everyone in the room has the same blood type. This is dependent on the fact that there must at least be another person in the room aside from the first and second person who are sent out in turn.

Hence, the assumption of the inductive step is that $k+1\ge 3$ , which implies that the assumption of the inductive hypothesis is that $k\ge 2$ .

So, the simplest version of the inductive hypothesis is for $k=2$ , which does not connect with the base case which is for $k=1$ .

This is where the proof went wrong.

Conclusion:

It has been explained where the proof went wrong.