# Flaw in this proof by induction

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?

• 2n=2(a+b) for some integers a and b where 0≤a,b<n won't work when n = 1. – steven gregory Sep 16 '15 at 16:07

## 2 Answers

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:

$2n=2(a+b)$ for some integers $a$ and $b$ where $0\le a,b<n$.

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$.

• if $0 \le a, b \lt 1$, then how can we assume that $a=b=0$? Can't $a$ be greater than 0? i.e be equal to $1$ and therefore it would be $2n = 2(1+0)$? Sorry if it's a stupid question, but the rest of your answer makes sense to me – cp101020304 Sep 16 '15 at 9:22
• @cp101020304: How is $a=1<1$? That value of $a$ violates $0\leq a,b<1$. – String Sep 16 '15 at 9:23
• Why does $a$ have to be less than $1$? @String – cp101020304 Sep 16 '15 at 9:24
• @cp101020304: Because the expression $0\le a,b<1$ is an abbreviation for $0\le a<1$ and $0\le b<1$; it’s not a pair of independent statements, $0<a$ and $b<1$. – Brian M. Scott Sep 16 '15 at 9:25
• @BrianM.Scott ohhhh, okay that clears it up! I did not know that D: Thank you good sir – cp101020304 Sep 16 '15 at 9:28

How do you write $1$ as $a+b$ where $0 \leq a,b < 1$?

• $a = 1$ and $b=0$ ? – cp101020304 Sep 16 '15 at 9:14
• See the strict inequality on the right-hand-side? – Sam Cappleman-Lynes Sep 16 '15 at 9:15