I'm trying to find a flaw in the following proof, but I am unsure if I am correct or not:
Identify the flaw in the proof that $2n = 0$ for all $n \ge 0$.
Base case: If $n=0$ then $2\cdot n = 2\cdot 0 = 0$
Inductive step: Assume $n \gt 0$ and $2m=0$ for all integers $m$ where $0 \le m \lt n$. Then we have
$2n = 2(a + b)$ for some integers a and b where $0 \le a, b \lt n$
$= 2a + 2b$
$= 0 + 0$
$= 0$
The part of the proof that seems incorrect to me is the fact that $b \lt n$, but the proof says $b=0$. For b to be less than n, it must be less than 0 according to the initial theorem.
Is this the only flaw in the proof?
Best Answer
The proof does not say that $b=0$; it says that because $b<n$, the induction hypothesis implies that $2b=0$. The problem comes at the very beginning:
When $n=1$ that simply isn’t true: if $0\le a,b<1$, then $a=b=0$, and $a+b\ne 1$ after all. Thus, the induction step can’t be carried out to get from $n=0$ to $n=1$.
If that first case of the induction step were valid, the argument would go through just fine, because if $n$ is an integer greater than $1$, it’s true that we can write $n=a+b$ for some $a$ and $b$ such that $0\le a,b<n$; for instance, we can let $a=1$ and $b=n-1$.