Today, we will learn about mathematical induction. We usually use induction to prove a certain statement to be correct for all natural numbers.
Let us use $P(n)$ to denote a statement that involves a natural number $n$. To prove that $P(n)$ is correct for all natural number $n$, an induction proof will have the following steps
Step 1: is called the initial step. We will prove that the statement $P(n)$ is correct for the case $n=0$.
Step 2: is called the induction step. This is the most important step. In this step,
- we assume that for any $0 \leq n \leq k$, the statement $P(n)$ is correct;
- with this assumption, we will prove that the statement $P(n)$ is also correct for the case $n=k+1$.
With these two steps, by the mathematical induction principle, we conclude that the statement $P(n)$ must be correct for all natural number $n$.
Let us now use mathematical induction to solve our first problem.
Problem 1. Prove that $$1 + 3 + 5 + 7 + \dots + (2n+1) = (n+1)^2.$$
Solution. We will prove by induction on variable $n$ that $$1 + 3 + 5 + 7 + \dots + (2n+1) = (n+1)^2.$$
Step 1. With $n=0$, we have $$1 = (0+1)^2$$
So the formula is correct for the case $n=0$.
Step 2. Assume that for any $0 \leq n \leq k$, the formula is correct. We will prove that the formula is also correct for the case $n=k+1$, that is, $$1 + 3 + 5 + 7 + \dots + (2k+1) + (2k+3) = (k+2)^2.$$
Indeed, by the induction assumption, the formula is correct for the case $n=k$, so we have $$1 + 3 + 5 + 7 + \dots + (2k+1) = (k+1)^2.$$
It follows that $$1 + 3 + 5 + 7 + \dots + (2k+1) + (2k+3) = (k+1)^2 + (2k+3) = k^2 + 4k + 4 = (k+2)^2.$$
Therefore, the formula is correct for the case $n=k+1$.
By the mathematical induction principle, the formula is correct for any natural number $n$. $\blacksquare$
We now know how to prove by induction. To prove that $P(n)$ is correct for all natural numbers $n$,
- we show that $P(0)$ is correct
- we prove that if $P(0), P(1), \dots, P(k)$ are correct then $P(k+1)$ is also correct.
The induction step (step 2) is the most important step because by this step,
- since $P(0)$ is correct, we conclude that $P(1)$ is correct
- since $P(0), P(1)$ are correct, we conclude that $P(2)$ is correct
- since $P(0), P(1), P(2)$ are correct, we conclude that $P(3)$ is correct
- since $P(0), P(1), P(2), P(3)$ are correct, we conclude that $P(4)$ is correct
- etc...
Let us solve some more problems to get used to the method.
Problem 2. Prove that for any natural number $n$, there always exist two integers $x$ and $y$ such that $$x^2 - 2012 y^2 = 13^n.$$
Solution. We will prove by induction on $n$ the following statement
There exist integers $x$ and $y$ such that $x^2 - 2012 y^2 = 13^n$.
With $n=0$, we have $$13^0 = 1 = 1^2 - 2012 \times 0^2 .$$
So the above statement is correct for the case $n=0$.
Assume that for any $0 \leq n \leq k$, the statement is correct. We will prove that the statement is also correct for the case $n=k+1$, i.e., we will show that there exist two integers $x$ and $y$ that satisfy $$x^2 - 2012 y^2 = 13^{k+1} .$$
Indeed, by the induction assumption, the statement is correct for the case $n=k$, so there exist two integers $a$ and $b$ that satisfy $$a^2 - 2012 b^2 = 13^k$$
We also have $$45^2 - 2012 \times 1^2 = 13$$Using the following identity $$(u^2 - d v^2)(s^2 - d t^2) = (us + d vt)^2 - d (ut + vs)^2$$ we obtain $$13^{k+1} = (a^2 - 2012 b^2)(45^2 - 2012 \times 1^2) = (45a + 2012 b)^2 - 2012 (a + 45b)^2.$$
Thus, we have proved the above statement is correct for the case $n=k+1$.
By the mathematical induction principle, for any natural number $n$, there always exist two integers $x$ and $y$ satisfying $13^n = x^2 - 2012 y^2$. $\blacksquare$
In the next problem, the initial step is for $n=5$ instead of $n=0$.
Problem 3. Prove that for any natural number $n \geq 5$, we have $2^n > n^2$.
Solution. We will prove by induction that for any $n \geq 5$, $$2^n > n^2 .$$
With $n =5$, we have $$2^5 = 32 > 5^2 = 25$$
So the inequality is correct for the case $n=5$.
Indeed, by the induction assumption, the inequality is correct for the case $n=k$, so we have $$2^k > k^2.$$
Therefore, $$2^{k+1} = 2 \times 2^k > 2k^2 = (k+1)^2 + (k-1)^2 -2 .$$
Since $k \geq 5$, we have $(k-1)^2 -2 > 0$, thus, $$2^{k+1} > (k+1)^2.$$
This proves that the inequality is correct for the case $n=k+1$. By the mathematical induction principle, the inequality $2^n > n^2$ is correct for any natural number $n \geq 5$. $\blacksquare$
In the next problem, the initial step is for $n=5$ instead of $n=0$.
Problem 3. Prove that for any natural number $n \geq 5$, we have $2^n > n^2$.
Solution. We will prove by induction that for any $n \geq 5$, $$2^n > n^2 .$$
With $n =5$, we have $$2^5 = 32 > 5^2 = 25$$
So the inequality is correct for the case $n=5$.
Suppose that the inequality is correct for any $5 \leq n \leq k$. We will prove that the inequality is also correct for the case $n=k+1$.
Indeed, by the induction assumption, the inequality is correct for the case $n=k$, so we have $$2^k > k^2.$$
Therefore, $$2^{k+1} = 2 \times 2^k > 2k^2 = (k+1)^2 + (k-1)^2 -2 .$$
Since $k \geq 5$, we have $(k-1)^2 -2 > 0$, thus, $$2^{k+1} > (k+1)^2.$$
This proves that the inequality is correct for the case $n=k+1$. By the mathematical induction principle, the inequality $2^n > n^2$ is correct for any natural number $n \geq 5$. $\blacksquare$
See you again in the next post when we use induction to solve some more problems.
Homework.
1. Prove that $$1!1 + 2!2 + 3!3 + \dots + n!n = (n+1)! - 1 .$$
2. Prove that for any natural number $n$, there always exist two integers $x$ and $y$ such that $$x^2 + y^2 = 5^n.$$
3. Prove that $$\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \dots + \frac{1}{n^2} \leq 2 - \frac{1}{n}.$$
Homework.
1. Prove that $$1!1 + 2!2 + 3!3 + \dots + n!n = (n+1)! - 1 .$$
2. Prove that for any natural number $n$, there always exist two integers $x$ and $y$ such that $$x^2 + y^2 = 5^n.$$
3. Prove that $$\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \dots + \frac{1}{n^2} \leq 2 - \frac{1}{n}.$$