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.