Mathematical induction

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...

So for any value of $n$, by induction step, we can deduce that $P(n)$ is correct.




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$.

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}.$$