Flawed Induction Proofs

We start by listing several flawed induction proofs. You should work through them and figure out what went wrong. You can jump to the end to see rebuttals of the proofs.

$$
The following is adapted from "No horse is of a different color," attributed to Polya.

Claim 1: In a group of $n$ people, everyone has the same name.

Proof: Let's show that the base case is true. In a group of $n=1$ people, all of them have the same name.

Let's show that induction step holds. Since the positive integer $k$ is in the set, this means that in a group of any $k$ people, all of them have the same name. So let's consider a group of $k+1$ people. Since the first $k$ people have the same name, and the last $k$ people also have the same name, it means that all $k+1$ of them must have the same name.

Thus, by mathematical induction, the set $S$ includes all positive integers, so in a group of $n$ people, everyone has the same name.
In particular, since my name is Calvin, and you are in the set of all $N$ people on Earth, it follows that your name is also Calvin. $_\square$

$$
The following is adapted from "Sorites paradox," attributed to Eubulides of Miletus.

Claim 2: Every positive integer $n$ is a whole lot less than $1, 000, 000$.

Proof: Base case. $1$ is certainly a whole lot less than $1,000,000$.

Induction step. If the positive integer $k$ is a whole lot less than $1,000,000$, then certainly $k+ 1$, which is just slightly bigger than $k$, is still a whole lot less than $1,000,000$.

Hence, by mathematical induction, the statement is true for all positive integers.
In particular, a billion is a whole lot less than a million. $_\square$

Claim 3: For every non-negative number $n$, $2 \times n = 0$.

Proof: Base case. $n = 0$. Clearly $2 \times n = 0$.

Induction step. Say it holds for $k$, and consider $k + 1$. Write $k + 1 = i + j$, where $i$ and $j$ are non-negative numbers. Then,

$$2 (k+1 ) = 2 (i + j ) = 2i + 2j = 0 + 0 = 0.$$

Hence, by mathematical induction, the statement is true for all non-negative integers.
In particular, $2 \times 1 = 0$. $_\square$

$$
The following is adapted from the "unexpected hanging paradox."

Claim 4: Suppose you are informed by your teacher that you will have a test next week, and it will take you by surprise. Then the test can never occur.

Proof: Let us induct backwards.

If it doesn't happen by Thursday, then it must happen on Friday. But that will not be a surprise. So it must happen by Thursday.
If it doesn't happen by Wednesday, then it must happen on Thursday. But that will not be a surprise. So it must happen by Wednesday.
If it doesn't happen by Tuesday, then it must happen on Wednesday. But that will not be a surprise. So it must happen by Tuesday.
If it doesn't happen by Monday, then it must happen on Tuesday. But that will not be a surprise. So it must happen by Monday.
If it happens on Monday, you already predicted it and are not surprised.
Hence, the test can never occur. $_ \square$

Rebuttal of Claim 1: The place the proof breaks down is in the induction step with $k = 1$. The problem is that when there are $k + 1 = 2$ people, the first $k = 1$ has the same name and the last $k=1$ has the same name. However, as there is no overlap, we cannot conclude that both of them have the same name. $_\square$

Rebuttal of Claim 2: The issue is partly in the ambiguity of the phrase "a whole lot less." Even though something is "a whole lot less," we can add a small amount "a whole lot" of times, and it will eventually become greater. That is what we are doing, adding 1 many many times, till it becomes greater than a million. $_\square$

Rebuttal of Claim 3: The problem comes with writing $k+1 = i + j$. It assumes that it can be written as the sum of 2 strictly smaller non-negative integers. While this is true of most cases, it is not true for $k = 0$. The number $0 + 1$ cannot be written as the sum of 2 strictly smaller non-negative integers. As such, to prove the statement that $2 \times 1 = 0$, we needed to make the assumption that $2 \times 1 = 0$. $_\square$