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?

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

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

  • 1
    $\begingroup$ 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 $\endgroup$ – cp101020304 Sep 16 '15 at 9:22
  • 1
    $\begingroup$ @cp101020304: How is $a=1<1$? That value of $a$ violates $0\leq a,b<1$. $\endgroup$ – String Sep 16 '15 at 9:23
  • 1
    $\begingroup$ Why does $a$ have to be less than $1$? @String $\endgroup$ – cp101020304 Sep 16 '15 at 9:24
  • 3
    $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Sep 16 '15 at 9:25
  • $\begingroup$ @BrianM.Scott ohhhh, okay that clears it up! I did not know that D: Thank you good sir $\endgroup$ – cp101020304 Sep 16 '15 at 9:28

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.