Given a wrong proof

Question

Given a wrong proof by induction.

Let us prove by induction that $n = 2n$ for all nonnegative integers $n$.

Let $P(n)$ denote the induction hypothesis that $n=2n$

Base case: For $n=0, 0=2*0=0$, thus $P(n)$ holds.

Inductive step: Assume that $P(n)$ holds for all nonnegative integers $n$. Now if we multiple both sides of the equation $n=2n$ by $\frac{n+1}{n}$, we get $n\frac{n+1}{n}=2n\frac{n+1}{n}$, so $n+1=2(n+1)$. Thus $P(n+1)$ holds and this completes the proof by induction.

I guess the wrong part is multiplying by $\frac{n+1}{n}$, because $n$ can be $0$, however I am not sure, can someone tell what is wrong with this proof?

Answer 1

You found the answer all by yourself: if $n=0$, $\frac{n+1}n$ makes no sense.

Answer 2

Let's try to prove it by strong induction:

The base case $n = 0$ is correct.

Assume that for some $n \in \mathbb{N}_0$ we have $k = 2k$ for all $k \in \{0, \ldots, n\}$.

Let's prove that $n+1 = 2(n+1)$.

$$n+1 \stackrel{k=n}= 2n + 1 \stackrel{k=1}= 2n + 2 = 2(n+1)$$

We first used the assumption for $k = n$ and then for $k = 1$.

Done.

Can you spot the mistake now?