Mathematical Induction

By the end of this lesson, you will be able to prove statements about positive integers using the Principle of Mathematical Induction — base case, inductive hypothesis, inductive step.

The Big Idea

Mathematical induction is how mathematicians prove statements that hold for all positive integers (or all integers beyond some starting point). It's not "guessing and checking" — it's a rigorous two-step proof that is logically equivalent to an infinite chain of implications.

The analogy: dominoes. If the first domino falls (base case) and every domino knocks over the next (inductive step), then ALL dominoes fall.

The Principle of Mathematical Induction

To prove $P(n)$ is true for all $n \geq 1$:

Step 1 (Base Case): Prove $P(1)$ is true.

Step 2 (Inductive Step): Assume $P(k)$ is true (the inductive hypothesis). Prove $P(k+1)$ is true.

Conclusion: By induction, $P(n)$ is true for all $n \geq 1$.

Example 1 — Sum Formula

Prove: $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ for all $n \geq 1$.

Base case: $n = 1$: LHS = 1; RHS = $1(2)/2 = 1$. ✓

Inductive step: Assume $1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}$.

Prove: $1 + 2 + \cdots + k + (k+1) = \dfrac{(k+1)(k+2)}{2}$.

Starting from the inductive hypothesis:

$\underbrace{1 + 2 + \cdots + k}_{k(k+1)/2} + (k+1) = \dfrac{k(k+1)}{2} + (k+1)$

$= (k+1)\left(\dfrac{k}{2} + 1\right) = (k+1)\dfrac{k+2}{2} = \dfrac{(k+1)(k+2)}{2}$ ✓

By induction, the formula holds for all $n \geq 1$. ∎

Example 2 — Sum of Squares

Prove: $\displaystyle\sum_{i=1}^{n} i^2 = \dfrac{n(n+1)(2n+1)}{6}$

Base case: $n = 1$: $1 = \frac{1 \cdot 2 \cdot 3}{6} = 1$ ✓

Inductive step: Assume true for $n = k$. Then:

$\sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2$

$= \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} = \frac{(k+1)[k(2k+1) + 6(k+1)]}{6}$

$= \frac{(k+1)(2k^2 + 7k + 6)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}$

which is the formula with $n = k+1$. ✓ ∎

Example 3 — Divisibility