1.9 Mathematical Induction

1. Discussion

Induction is a smart technique used to prove propositions of the form "For any $n \in \mathbb{N}$, it holds $P(n)$" or "For any $n \ge 1$, it holds $P(n)$", where $P(n)$ is a statement depending on a natural number $n$.

Example: For any $n \ge 1$, it holds:

$$1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$$

There are several ways to prove this relation (for example, using the sum $S_n$ for the arithmetic sequence with $u_1=1$ and $d=1$). However, this is a good example to explain induction. One way to persuade ourselves about the validity of this relation is to check for several values of $n$:

  • For $n=1$: $\text{LHS} = 1$, $\text{RHS} = \dfrac{1(2)}{2} = 1$. (The result is true!)
  • For $n=2$: $\text{LHS} = 1+2=3$, $\text{RHS} = \dfrac{2(3)}{2} = 3$. (The result is true!)
  • For $n=3$: $\text{LHS} = 1+2+3=6$, $\text{RHS} = \dfrac{3(4)}{2} = 6$. (The result is true!)
  • For $n=4$: $\text{LHS} = 1+2+3+4=10$, $\text{RHS} = \dfrac{4(5)}{2} = 10$. (The result is true!)

Notice: But this is not a proof. It is just an indication that the statement is true. The induction technique provides a rigorous, complete proof.

2. The Method of Mathematical Induction

The technique consists of three distinct steps:

  1. Basis Step: Show that the statement is true for $n=1$ (or the first possible value).
  2. Assumption Step: Assume that the statement is true for $n=k$ (for some $k$).
  3. Inductive Step: Prove that the statement is true for $n=k+1$, based strictly on the assumption of step 2.

Logic of the Method (The Domino Effect):
Roughly speaking, we construct a mechanism which uses the outcome for $k$, to prove the next outcome for $k+1$. Step 1 is necessary to switch on the mechanism!

  • Hence, we have the initial outcome for $n=1$.
  • Based on that, we obtain the next outcome for $n=2$.
  • Based on that, we obtain the next outcome for $n=3$, and so on (we automatically obtain the result for any $n$).

3. Examples

EXAMPLE 1

Prove by mathematical induction that $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ for any $n \ge 1$.

Proof:

Step 1: For $n=1$ the statement is true. Indeed, $\text{LHS} = 1$, $\text{RHS} = \dfrac{1(1+1)}{2} = 1$.
Step 2: Assume the statement is true for $n=k$, that is:
$$1 + 2 + 3 + \dots + k = \dfrac{k(k+1)}{2}$$
Step 3: We prove that the statement is true for $n=k+1$, that is:
$$1 + 2 + \dots + k + (k+1) = \dfrac{(k+1)(k+2)}{2}$$
$$\begin{aligned} \text{LHS} &= (1 + 2 + \dots + k) + (k+1) \\ &= \dfrac{k(k+1)}{2} + (k+1) \quad \text{[by assumption]} \\ &= (k+1)\left(\dfrac{k}{2} + 1\right) \\ &= (k+1)\left(\dfrac{k+2}{2}\right) \\ &= \dfrac{(k+1)(k+2)}{2} \quad (= \text{RHS}) \end{aligned}$$
Conclusion: Therefore, by mathematical induction, the statement is true for any $n \ge 1$.

EXAMPLE 2 (Divisibility)

Show that $6^n - 1$ is divisible by 5, for any $n \ge 1$.

Proof:

Step 1: For $n=1$, $6^1 - 1 = 5$, which is divisible by 5. True.
Step 2: Assume the statement is true for $n=k$.
Assume $6^k - 1$ is divisible by 5, i.e., $6^k - 1 = 5m$ for some $m \in \mathbb{Z}$ $\implies 6^k = 5m+1$.
Step 3: We prove that the statement is true for $n=k+1$, that is $6^{k+1}-1$ is divisible by 5.
$$\begin{aligned} 6^{k+1} - 1 &= 6 \cdot 6^k - 1 \\ &= 6(5m + 1) - 1 \quad \text{[by assumption]} \\ &= 30m + 6 - 1 \\ &= 30m + 5 \\ &= 5(6m + 1) \end{aligned}$$
Which is clearly divisible by 5 (Q.E.D). Therefore, by mathematical induction, the statement is true for any $n \ge 1$.

EXAMPLE 3 (Inequality)

Prove by mathematical induction that $n! > 2^n$ for any $n \ge 4$.
(We may easily verify that the result is not true for $n=1, 2, 3$).

Proof: Sometimes the induction does not begin from $n=1$.

Step 1: For $n=4$, the statement is true. Indeed, $\text{LHS} = 4! = 24$, $\text{RHS} = 2^4 = 16$. Since $24 > 16$, it is true.
Step 2: Assume that the statement is true for $n=k$, that is $k! > 2^k$.
Step 3: Prove for $n=k+1$, i.e. $(k+1)! > 2^{k+1}$.
$$\begin{aligned} \text{LHS} = (k+1)! &= (k+1) \cdot k! \\ &> (k+1) \cdot 2^k \quad \text{[by assumption]} \end{aligned}$$
Since $n \ge 4 \implies k \ge 4$, it holds that $k+1 > 2$. Therefore:
$$(k+1)2^k > 2 \cdot 2^k = 2^{k+1}$$
Thus $(k+1)! > 2^{k+1}$. By mathematical induction, the statement is true for any $n \ge 4$.

EXAMPLE 4 (Sequences)

Consider the sequence $u_1=0$, $u_{n+1} = 2u_n + 2$.

(a) The first 6 terms are: $0, 2, 6, 14, 30, 62$. (The sequence is neither arithmetic nor geometric).
(b) Look at the first 6 powers of 2: $2, 4, 8, 16, 32, 64$. We notice that each term is exactly $2$ less than the corresponding power of 2. So we guess that $u_n = 2^n - 2$.
(c) Proof by Induction: Prove that your guess is true.

Step 1: For $n=1$, $u_1 = 2^1 - 2 = 0$. True.
Step 2: Assume $u_k = 2^k - 2$.
Step 3: Prove $u_{k+1} = 2^{k+1} - 2$.
$$\begin{aligned} u_{k+1} &= 2u_k + 2 \quad \text{[by definition]} \\ &= 2(2^k - 2) + 2 \quad \text{[by assumption]} \\ &= 2^{k+1} - 4 + 2 \\ &= 2^{k+1} - 2 \end{aligned}$$
Therefore, by mathematical induction, the statement is true for any $n \ge 1$.

EXAMPLE 5 (Fibonacci & Two-Step Induction)

Consider the Fibonacci sequence $u_1=1, u_2=1, u_{n+2} = u_n + u_{n+1}$ (which generates $1, 1, 2, 3, 5, 8, 13, 21, \dots$). Prove by induction that $u_n < 2^n$ for any $n \ge 1$.

Proof: Sometimes, we must assume two preceding steps in order to prove the next step.

Step 1: For $n=1$ and $n=2$ the statement is true. Indeed, $u_1 = 1 < 2^1$ and $u_2 = 1 < 2^2$.
Step 2: We assume that the statement is true for $n=k$ AND $n=k+1$, i.e., $u_k < 2^k$ and $u_{k+1} < 2^{k+1}$.
Step 3: We prove that the statement is true for $n=k+2$, i.e. $u_{k+2} < 2^{k+2}$.
$$\begin{aligned} u_{k+2} &= u_k + u_{k+1} \quad \text{[by definition]} \\ &< 2^k + 2^{k+1} \quad \text{[by assumption]} \end{aligned}$$
It suffices to show that $2^k + 2^{k+1} \le 2^{k+2}$:
$$\begin{aligned} 2^k + 2^{k+1} &\le 2^{k+2} \\ \Leftrightarrow 1 + 2 &\le 4 \quad \text{[dividing by } 2^k \text{]} \\ \Leftrightarrow 3 &\le 4 \end{aligned}$$
Which is true! Thus $u_{k+2} < 2^{k+2}$. By mathematical induction, the statement is true for any $n \ge 1$.

⚠️ NOTICE: Transitioning from $k$ to $k+1$

The critical step is the connection between the $(k+1)$-statement and the $k$-statement, in order to embed the assumption into the proof. We may use the following table as a guide:

If statement involves... Notation Relation to use
Power $a^n$ $a^{k+1} = a^k \cdot a$
Factorial $n!$ $(k+1)! = k! \cdot (k+1)$
Sum $\sum_{r=1}^{n} u_r$ $\sum_{r=1}^{k+1} u_r = \left(\sum_{r=1}^{k} u_r\right) + u_{k+1}$
Derivative $\dfrac{d^n y}{dx^n}$ $\dfrac{d^{k+1}y}{dx^{k+1}} = \dfrac{d}{dx}\left(\dfrac{d^k y}{dx^k}\right)$
Matrix $A^n$ $A^{k+1} = A^k \cdot A$