3
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ There is also another mistake: in the inductive step you assume that $P(n)$ holds for all nonnegative integers $n$. That's not how induction works. You should fix $n$ and assume that $P(n)$ holds instead. $\endgroup$
    – Adayah
    Sep 21, 2017 at 15:56
  • $\begingroup$ Right, it fails by trying to scale $\,0=2(0)\,$ by $1/\color{#c00}{0}\,$ to get $\,1 = 2(1)\ \ $ $\endgroup$ Sep 21, 2017 at 18:24
  • $\begingroup$ You've already figured out the answer to your question. $\endgroup$ Oct 20, 2018 at 3:12

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .