1.9 Mathematical InductionHL Only

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} \\ \iff 1 + 2 &\le 4 \quad \text{[dividing by } 2^k \text{]} \\ \iff 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$.