What is wrong with this induction proof? I am confused on how this is wrong other than the base case being wrong.

120 Views Asked by At

P(n): $n=2n$ for all integers $n >= 0$

Base Case: n = 0

  • Verify Base Case:

    P(0): 0 = 2(0) which is true

  • Induction Step:

    Assume that P(n) is true. Then multiply both sides of the quantity by $(n+1)/n$ which gives us $n+1=2(n+1)$ = $P(n+1)$

I am not sure what exactly makes this proof wrong despite me knowing it is false.

3

There are 3 best solutions below

0
On BEST ANSWER

You have divided by $n$ in your induction step where you have multiplied by $(n+1)/n$

Note that you may not divide by $n=0$ but your initial step was involving $n=0$

Thus your argument fails at $$P(0)\implies P(1)$$

0
On

When applying the inductive step for the first time with $n=0$, you are instructed to multiply by $\frac{n+1}{n}=\frac{1}{0}$. Clearly, this is not a well defined number and, hence, not a well-defined step.

0
On

What makes the proof wrong is that, when $n=0$, you cannot multiply by $(n+1)/n$,

because that would involve dividing by $0$, so it is not allowed.

For a different kind of induction fallacy, see this Wikipedia article.