Mathematical Induction

When studying the world around us, we often draw conclusions based on the results of observations and experiments. General conclusions obtained by examining individual cases are called inductive, and the method of such reasoning is called the inductive method or induction (from Latin inductio — derivation).

For example, long before the discovery of the laws of Earth’s motion, people concluded that the Sun rises in the east in the morning and sets in the west in the evening. This conclusion is inductive: it was based solely on observations.

Of course, induction does not always lead to correct conclusions. Despite the need to treat inductive conclusions with a certain degree of caution, the inductive method finds wide application in mathematics.

Inductive Conjectures

Let us consider two examples.

✎Example — Sum of Odd Numbers

Statement. Let us try to identify a pattern in the sums $S_n$ of the first $n$ odd natural numbers.

Solution.

S_1 = 1 = 1;\quad S_2 = 1 + 3 = 4;\quad S_3 = 1 + 3 + 5 = 9;

S_4 = 1 + 3 + 5 + 7 = 16;\quad S_5 = 1 + 3 + 5 + 7 + 9 = 25.

The numbers 1, 4, 9, 16, 25 are perfect squares of consecutive natural numbers. We can now make the following conjecture (inductive conclusion): for any natural number $n$

S_n = n^2.

✎Example — The Polynomial f(n) = n² - n + 41

Statement. Consider the values of the polynomial $f(n) = n^2 - n + 41$ for $n = 1, 2, 3, 4, 5$ .

Solution.

$f(1) = 41$ — prime; $f(2) = 43$ — prime; $f(3) = 47$ — prime; $f(4) = 53$ — prime; $f(5) = 61$ — prime.

One might conjecture that $f(n)$ is prime for every natural number $n$ . However, this conjecture is false: $f(41) = 41^2 - 41 + 41 = 41^2$ — a composite number.

ℹNote — Inductive Conclusions

Both conjectures above are merely hypotheses that need to be either proved or disproved. A hypothesis can be disproved by a counterexample, but verifying a finite number of cases can never prove a statement that must hold for infinitely many values.

The Method of Mathematical Induction

The method of proof described below is called mathematical induction. In general terms, it can be described as follows.

Suppose we need to prove that a certain statement is true for every natural number $n$ .

⚡Theorem — The Method of Mathematical Induction

A proof by mathematical induction consists of two parts (theorems):

Base case: Verify that the statement is true for $n = 1$ .
Inductive step: Assume the statement is true for $n = k$ , and on this basis prove that it is true for $n = k + 1$ .

Both steps are essential. As we saw above, a statement can be true in many individual cases but still be false in general.

ℹNote — Importance of the Base Case

It would be a mistake to consider the base case less important than the inductive step. For instance, using only the inductive step, one could “prove” that for every natural number $n$ , the number $2n + 1$ is even. Assume this holds for $n = k$ , i.e., $2k + 1$ is even. Then $2(k+1) + 1 = (2k+1) + 2$ . The sum of two even numbers is even. We have thus “proved” the inductive step — but the base case fails since $2 \cdot 1 + 1 = 3$ is odd.

Examples of Proofs

✎Example 1 — Sum of Fractions

Statement. Derive a formula for the sum

\frac{1}{1 \cdot 3} + \frac{7}{3 \cdot 5} + \ldots + \frac{2n^2 - 1}{(2n-1)(2n+1)}, \quad n \in \mathbb{N}.

Solution. For $n = 1$ : $S_1 = \dfrac{1}{1 \cdot 3} = \dfrac{1}{3}$ .

For $n = 2$ : $S_2 = \dfrac{1}{1 \cdot 3} + \dfrac{7}{3 \cdot 5} = \dfrac{4}{5}$ .

For $n = 3$ : $S_3 = \dfrac{9}{7}$ . For $n = 4$ : $S_4 = \dfrac{16}{9}$ .

We conjecture that for all $n \in \mathbb{N}$ :

S_n = \frac{n^2}{2n+1}.

We prove this by mathematical induction. The base case $n = 1$ has been verified above.

Assume the formula holds for $n = k$ , i.e., $S_k = \dfrac{k^2}{2k+1}$ .

Then:

S_{k+1} = S_k + \frac{2(k+1)^2 - 1}{(2k+1)(2k+3)} = \frac{k^2}{2k+1} + \frac{2k^2 + 4k + 1}{(2k+1)(2k+3)} = \frac{(k+1)^2}{2k+3} = \frac{(k+1)^2}{2(k+1)+1}.

Thus the formula holds for $n = k + 1$ .

Answer: $S_n = \dfrac{n^2}{2n+1}$ .

✎Example 2 — Sum of the First n Natural Numbers

Statement. Prove that $1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2}$ for $n \in \mathbb{N}$ .

Solution. Prove this equality independently using mathematical induction.

✎Example 3 — Sum of Cubes

Statement. Derive a formula for $1^3 + 2^3 + 3^3 + \ldots + n^3$ , where $n \in \mathbb{N}$ .

Solution. For $n = 1$ : $S_1 = 1$ . For $n = 2$ : $S_2 = 9 = (1 + 2)^2$ . For $n = 3$ : $S_3 = 36 = (1 + 2 + 3)^2$ . For $n = 4$ : $S_4 = 100 = (1 + 2 + 3 + 4)^2$ .

Using Example 2, we can write the conjecture as:

S_n = \left(\frac{n(n+1)}{2}\right)^2.

The base case $n = 1$ has been verified. Assume the formula holds for $n = k$ , i.e., $S_k = \left(\dfrac{k(k+1)}{2}\right)^2$ .

Then:

S_{k+1} = \left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3 = (k+1)^2\left(\frac{k^2}{4} + k + 1\right) = (k+1)^2 \cdot \frac{(k+2)^2}{4} = \left(\frac{(k+1)(k+2)}{2}\right)^2.

Thus the formula holds for $n = k + 1$ .

Answer: $1^3 + 2^3 + \ldots + n^3 = \left(\dfrac{n(n+1)}{2}\right)^2$ .

✎Example 4 — Divisibility by 4

Statement. Prove that for any $n \in \mathbb{N}$ , the expression $5^n - 3^n + 2n$ is divisible by 4.

Solution. For $n = 1$ : $5^1 - 3^1 + 2 = 4$ , which is divisible by 4. The base case is established.

Assume the statement holds for $n = k$ , i.e., $(5^k - 3^k + 2k)$ is divisible by 4.

We need to show that $(5^{k+1} - 3^{k+1} + 2(k+1))$ is also divisible by 4.

Consider the difference:

(5^{k+1} - 3^{k+1} + 2k + 2) - (5^k - 3^k + 2k) = 5^k(5-1) - 3^k(3-1) + 2 = 4 \cdot 5^k - 2(3^k - 1).

Since $(3^k - 1)$ is divisible by 2, the entire expression is divisible by 4. Therefore the statement is true.

✎Example 5 — Bernoulli's Inequality

Statement. Prove the inequality (Bernoulli’s inequality):

(1 + x)^n \geqslant 1 + nx, \quad n \in \mathbb{N}, \; x > -1.

Solution. For $n = 1$ : $1 + x \geqslant 1 + x$ is clearly true.

Assume the inequality holds for $n = k$ : $(1 + x)^k \geqslant 1 + kx$ , $k \in \mathbb{N}$ . Since $1 + x > 0$ , we have $(1 + x)^{k+1} \geqslant (1 + kx)(1 + x)$ .

Now: $(1 + kx)(1 + x) = 1 + (k+1)x + kx^2 \geqslant 1 + (k+1)x$ .

Therefore $(1 + x)^{k+1} \geqslant 1 + (k+1)x$ .

Both the base case and the inductive step have been established. The inequality is proved.

Induction with a Different Base Value and Step

Mathematical induction is also used when a statement needs to be proved for all natural numbers $n \geqslant n_0$ , where $n_0 \in \mathbb{N}$ , $n_0 > 1$ . In this case, the base case is verified for $n = n_0$ .

It is also possible to use induction with step 2: the base case verifies the statement for both $n = 1$ and $n = 2$ , and the inductive step proves that if the statement holds for $n = k$ , it also holds for $n = k + 2$ .

✏Exercise — Prove by Mathematical Induction

Prove that for any natural number $n$ : $1^2 + 2^2 + 3^2 + \ldots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$ .
Prove the inequality $2^n > 2n + 1$ for $n \in \mathbb{N}$ , $n \geqslant 3$ .
Prove that for any natural number $n$ , the expression $(5^n - 3^n + 2n)$ is divisible by 4.