1.9 Mathematical Induction

1. Discussion

Induction is a technique used to prove propositions of the form "For any $n \in \mathbb{Z}^+$ 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 = \frac{n(n+1)}{2}$

One way to verify the validity of this relation is to check for several values of $n$:

  • For $n=1$: LHS $= 1$, RHS $= \frac{1(2)}{2} = 1$. (True)
  • For $n=2$: LHS $= 1+2=3$, RHS $= \frac{2(3)}{2} = 3$. (True)
  • For $n=3$: LHS $= 6$, RHS $= \frac{3(4)}{2} = 6$. (True)

However, this is just an indication, not a proof. The induction technique provides a rigorous proof.

2. The Method of Mathematical Induction

The technique consists of three 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 on the assumption of step 2.

Logic of the Method: Roughly speaking, a mechanism is constructed where the outcome for $k$ is used to prove the next outcome for $k+1$. Step 1 switches on the mechanism.

  • The initial outcome for $n=1$ is established.
  • Based on that, the outcome for $n=2$ is obtained.
  • Based on that, the outcome for $n=3$ is obtained, and so on.

3. Examples

EXAMPLE 1

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

Proof:

Step 1: For $n=1$ the statement is true. LHS $= 1$, RHS $= \frac{1(2)}{2} = 1$.
Step 2: Assume the statement is true for $n=k$:
$1 + 2 + 3 + \dots + k = \frac{k(k+1)}{2}$
Step 3: Prove the statement is true for $n=k+1$:
Required to show: $1 + 2 + \dots + k + (k+1) = \frac{(k+1)(k+2)}{2}$
LHS $= (1 + 2 + \dots + k) + (k+1)$
$= \frac{k(k+1)}{2} + (k+1)$ [by assumption]
$= (k+1)(\frac{k}{2} + 1)$
$= (k+1)\frac{k+2}{2} = \frac{(k+1)(k+2)}{2}$ (= RHS).
Conclusion: The statement is true for $n=1$ and assuming it is true for $n=k$, it is also true for $n=k+1$. 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}$.
Step 3: Prove for $n=k+1$.
$6^{k+1} - 1 = 6 \cdot 6^k - 1$
$= 6(5m + 1) - 1$ [Substituting $6^k = 5m+1$ from assumption]
$= 30m + 6 - 1$
$= 30m + 5 = 5(6m + 1)$.
This is clearly divisible by 5. Therefore, 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$.

Proof:

Step 1: For $n=4$: LHS $= 4! = 24$, RHS $= 2^4 = 16$. Since $24 > 16$, it is true.
Step 2: Assume true for $n=k$: $k! > 2^k$.
Step 3: Prove for $n=k+1$: $(k+1)! > 2^{k+1}$.
LHS $= (k+1)! = (k+1) \cdot k!$
$> (k+1) \cdot 2^k$ [by assumption]
Since $n \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}$. 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$. (Neither arithmetic nor geometric).

(b) Comparing with powers of 2 ($2, 4, 8, 16, 32, 64$), the general formula appears to be $u_n = 2^n - 2$.

(c) Proof by Induction:

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$.
$u_{k+1} = 2u_k + 2$ [Recursive definition]
$= 2(2^k - 2) + 2$ [By assumption]
$= 2^{k+1} - 4 + 2$
$= 2^{k+1} - 2$.
Q.E.D.

EXAMPLE 5 (Fibonacci & Two-Step Induction)

Consider the Fibonacci sequence $u_1=1, u_2=1, u_{n+2} = u_n + u_{n+1}$. Prove $u_n < 2^n$.

Proof: Sometimes assumptions for two preceding steps are needed.

Step 1: For $n=1$: $1 < 2^1$. For $n=2$: $1 < 2^2$. True.
Step 2: Assume true for $n=k$ ($u_k < 2^k$) AND $n=k+1$ ($u_{k+1} < 2^{k+1}$).
Step 3: Prove for $n=k+2$: $u_{k+2} < 2^{k+2}$.
$u_{k+2} = u_k + u_{k+1}$
$< 2^k + 2^{k+1}$ [by assumption]
Since $1 < 2^2$ (or generally $2^k < 3 \cdot 2^k$), we can simply show:
$2^k + 2^{k+1} = 2^k(1+2) = 3 \cdot 2^k < 4 \cdot 2^k = 2^2 \cdot 2^k = 2^{k+2}$.
Thus $u_{k+2} < 2^{k+2}$.

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

The critical step is connecting the $(k+1)$-statement to the $k$-statement. Use this guide:

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 = (\sum_{r=1}^{k} u_r) + u_{k+1}$
Derivative $\frac{d^n y}{dx^n}$ $\frac{d^{k+1}y}{dx^{k+1}} = \frac{d}{dx}(\frac{d^k y}{dx^k})$