In previous posts, we learned about mathematical induction and we used induction to solve some problems. We can see that mathematical induction is a useful technique in problem solving. Today, we will consider two induction proofs that lead to a wrong result that $$1 = 2012 = 2013$$ Let us know if you can identify the wrong steps in the proofs.

**Proving $1 = 2012$**

**Construct a sequence as follows: $$a_0 = 2012, ~~a_1 = 1, ~~a_{n+1} = 2 a_{n} - a_{n-1}. $$**

We will prove by induction on variable $n$ the following statement,

For any $m$ and $n$, it holds that $a_m = a_{m+1} = \dots = a_{m+n}$

For $n=0$, we have $$a_m = a_{m+0}$$

So the statement is correct for the case $n=0$.

Suppose that the statement is correct for any $0 \leq n \leq k$. We will prove that the statement is also correct for the case $n=k+1$, i.e., we will prove that $$a_m = a_{m+1} = \dots = a_{m+k+1}$$

Indeed, by induction assumption, the statement is correct for the case $n=k$, so $$a_{m} = a_{m+1} = \dots = a_{m+k}$$

Since the above equality holds for any value of $m$, we can substitute $m$ by $m+1$ and obtain

$$a_{m+1} = a_{m+2} = \dots = a_{m+1+k}$$

It follows that $$a_{m} = a_{m+1} = \dots = a_{m+k} = a_{m+k+1}$$

Thus, we have shown that the statement is correct for the case $n=k+1$.

By mathematical induction principle, the statement is correct for any $n$ and we have the following equality $$a_m = a_{m+1} = \dots = a_{m+n}$$

Let $m=0$ and $n=1$, we obtain the following equality $$a_0 = a_1$$

it means that $$2012 = 1$$

**Proving $1 = 2013$**

Using the same sequence as above $$a_0 = 2012, ~~a_1 = 1, ~~a_{n+1} = 2 a_{n} - a_{n-1}. $$

We prove by induction the following statement,

For any $n$, it holds that $a_n = n + 2012$

For $n=0$, we have $$a_0 = 2012 = 0 + 2012$$

So the statement is correct for the case $n=0$.

Suppose that the statement is correct for any $0 \leq n \leq k$. We will prove that the statement is also correct for the case $n=k+1$, i.e., we will prove that $$a_{k+1} = (k + 1) + 2012 = k + 2013$$

Indeed, by induction assumption, the statement is correct for the case $n=k-1$, so $$a_{k-1} = (k - 1) + 2012 = k + 2011$$

Also by induction assumption, the statement is correct for the case $n=k$, so $$a_k = k + 2012$$

It follows that $$a_{k+1} = 2 a_{k} - a_{k-1} = 2(k + 2012) - (k + 2011) = k + 2013$$

Thus, we have proved that the statement is correct for the case $n=k+1$.

By mathematical induction principle, the statement is correct for any value of $n$, and we have the following equality $$a_n = n + 2012$$

Let $n=1$, we obtain $$a_1 = 1 + 2012 = 2013$$

but by definition, $a_1 = 1$, so $$2013 = 1$$

See you again in the next post.

## No comments:

## Post a Comment