Today we will use induction to solve some more problems.
Problem 4. Prove that $$1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + n (n+1)(n+2) = \frac{1}{4} n(n+1)(n+2)(n+3).$$
Solution. We will prove by induction the following formula, $$1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + n (n+1)(n+2) = \frac{1}{4} n(n+1)(n+2)(n+3).$$
So the above formula is correct for the case $n=1$.
Assume that for any $1 \leq n \leq k$, the formula is correct. We will prove that the formula is also correct for the case $n=k+1$, i.e., we will prove that $$1 \times 2 \times 3 + \dots + k (k+1)(k+2) + (k+1)(k+2)(k+3) = \frac{1}{4} (k+1)(k+2)(k+3)(k+4).$$
Indeed, by induction assumption, the formula is correct for the case $n=k$, so $$1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + k (k+1)(k+2) = \frac{1}{4} k(k+1)(k+2)(k+3).$$
Hence, $$1 \times 2 \times 3 + \dots + k (k+1)(k+2) + (k+1)(k+2)(k+3) $$ $$= \frac{1}{4} k(k+1)(k+2)(k+3) + (k+1)(k+2)(k+3)$$ $$= \frac{1}{4} (k+1)(k+2)(k+3)(k+4).$$
We have proved that the formula is correct for the case $n=k+1$.
By the mathematical induction principle, the formula must be correct for any $n \geq 1$. $\blacksquare$
Problem 5. Prove that $$49 ~\mid~ 8^n + 42 n - 1.$$
Solution. We will prove by induction the following statement $$8^n + 42 n - 1 = 0 \pmod{49}$$
For $n=0$, we have $$8^0 + 42 \times 0 - 1 = 0$$
So the above statement is correct for the case $n=0$.
Assume 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 $$8^{k+1} + 42 (k+1) - 1 = 8^{k+1} + 42 k + 41 = 0 \pmod{49}.$$
Indeed, by the induction assumption, the statement is correct for the case $n=k$, so we have $$8^k + 42 k - 1 = 0 \pmod{49} .$$
Thus, $$8(8^k + 42 k - 1) = 8^{k+1} + 336 k - 8 = 0 \pmod{49} .$$
Therefore, $$8^{k+1} + 42 k + 41 = (8^{k+1} + 336 k - 8) - 49(6k - 1) = 0 \pmod{49} .$$
We have proved that the statement is correct for the case $n=k+1$.
By the mathematical induction principle, the statement must be correct for any natural number $n$. $\blacksquare$
In the above problems, we can see that in the induction step, in order to prove that $P(k+1)$ is correct, we only need to use the assumption that $P(k)$ is correct. We did not need to use the assumption that $P(0)$, $P(1)$, ..., $P(k-1)$ are correct.
In the next problem, we will see that in order to prove that $P(k+1)$ is correct, we need to use both the assumption that $P(k-1)$ is correct and the assumption that $P(k)$ is correct.
Problem 6. The Fibonacci sequence is determined as follows: $F_0 = 0$, $F_1 = 1$, $F_{n+1} = F_n + F_{n-1}$. Thus,
$$F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, \dots$$
Prove that the formula for Fibonacci sequence is
$$F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right]$$
Solution. Let $$\alpha = \frac{1 + \sqrt{5}}{2}, ~~ \beta = \frac{1 - \sqrt{5}}{2}.$$
We will prove by induction the following statement $$F_n = \frac{1}{\sqrt{5}} ( \alpha^n - \beta^n ) $$
For $n=0$, we have $$\frac{1}{\sqrt{5}} ( \alpha^0 - \beta^0 ) = 0 = F_0$$
Thus, the statement is correct for the case $n=0$.
For $n=1$, we have $$\frac{1}{\sqrt{5}} ( \alpha^1 - \beta^1 ) = \frac{1}{\sqrt{5}} \sqrt{5} = 1 = F_1$$
So the statement is also correct for the case $n=1$.
Suppose that the statement is correct for all the cases $0 \leq n \leq k$ where $k \geq 1$. We will prove that the statement is also correct for the case $n=k+1$, i.e. we will prove that $$F_{k+1} = \frac{1}{\sqrt{5}} ( \alpha^{k+1} - \beta^{k+1} ) $$
Indeed, since $0 \leq k-1 \leq k$, by the induction assumption, the statement is correct for the case $n=k-1$, thus, $$F_{k-1} = \frac{1}{\sqrt{5}} ( \alpha^{k-1} - \beta^{k-1} ) $$
Also by the induction assumption, the statement is correct for the case $n=k$, so $$F_{k} = \frac{1}{\sqrt{5}} ( \alpha^{k} - \beta^{k} ) $$
It follows that $$F_{k+1} = F_{k-1} + F_k = \frac{1}{\sqrt{5}} [ (\alpha^{k-1} + \alpha^{k}) - (\beta^{k-1} + \beta^{k})] $$ $$= \frac{1}{\sqrt{5}} [ \alpha^{k-1} (1 + \alpha) - \beta^{k-1} ( 1 + \beta)] $$
Observe that $\alpha$ and $\beta$ are the two roots of the equation $1+x=x^2$, so $1+\alpha=\alpha^2$ and $1+\beta=\beta^2$. It follows that $$F_{k+1} = \frac{1}{\sqrt{5}} ( \alpha^{k-1} \alpha^2 - \beta^{k-1} \beta^2 ) = \frac{1}{\sqrt{5}} ( \alpha^{k+1} - \beta^{k+1} )$$
So we have proved that the statement is correct for the case $n=k+1$.
By the mathematical induction principle, the statement must be correct for any natural number $n$. $\blacksquare$
In Problem 6, in order to prove that $P(k+1)$ is correct, we have to use two assumptions that $P(k-1)$ is correct and $P(k)$ is correct. Because of that, in the initial step, we have to verify that $P(0)$ is correct and $P(1)$ is correct. It then follows from the induction step that:
- because P(0), P(1) are correct, we conclude that P(2) is correct
- because P(0), P(1), P(2) are correct, we conclude that P(3) is correct
- because P(0), P(1), P(2), P(3) are correct, we conclude that P(4) is correct
- v.v...
Proving $1 > 2$
We will use induction to prove that $1 > 2$. Consider the following proof carefully to see if you can point out the wrong step in this proof.
Let us construct the following sequence: $a_0 = 1$, $a_1 = 1$, $a_{n+1} = a_{n-1} + a_n + 11$.
We will prove by induction the following statement
For any $n$, we have $a_n > 4 n - 2$
For $n=0$, we have $$a_0 = 1 > 4 \times 0 - 2 = -2$$
So the statement is correct for the case $n=0$.
Assume 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$, that is, we will prove $$a_{k+1} > 4(k+1) - 2 = 4k + 2$$
Indeed, by the induction assumption, the statement is correct for the case $n=k-1$, so
$$a_{k-1} > 4(k-1) - 2 = 4k - 6$$
Also by the induction assumption, the statement is correct for the case $n=k$, so
$$a_{k} > 4k - 2$$
It follows that
$$a_{k+1} = a_{k-1} + a_k + 11 > (4k - 6) + (4k - 2) + 11 = 8k + 3 > 4k + 2 $$
So we have proved that the statement is correct for the case $n=k+1$.
By the mathematical induction principle, the statement must be correct for any natural number $n$.
We have just proved the following inequality
$$a_n > 4 n - 2$$
With $n=1$, the inequality is
$$1 > 2$$
So what have we done wrong here?!
See you again in the next post when we solve some more problems by mathematical induction.
Homework
1. Generalize the following equality $$1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + n (n+1)(n+2) = \frac{1}{4} n(n+1)(n+2)(n+3).$$
2. Prove that $$25 ~\mid~ 6^n - 5n - 1$$
Try to generalize this.
3. With the Fibonacci sequence
$$F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, \dots$$
determine all values of $n$ such that $F_n > 3n$.