Mathematical induction: the 3-step method

The 3-step ritual

To prove property $P(n)$ holds for every integer $n \geq n_0$:

Step 1: Base case

Check $P(n_0)$ is true (often $n_0 = 0$ or $1$).

Step 2: Inductive step

Assume $P(n)$ true for some fixed $n \geq n_0$ (inductive hypothesis, IH). Prove $P(n + 1)$ is true.

Step 3: Conclusion

By induction, $P(n)$ holds for all $n \geq n_0$.

Example: $\displaystyle \sum_{k=1}^n k = \dfrac{n(n+1)}{2}$

Call $P(n)$: $1 + 2 + \ldots + n = n(n+1)/2$.

Base ($n = 1$): $1 = 1 \cdot 2 / 2$. ✓

Inductive: Assume $P(n)$. Show $P(n+1)$.

$1 + \ldots + n + (n+1) = \dfrac{n(n+1)}{2} + (n+1) = \dfrac{(n+1)(n+2)}{2}$ ✓

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

Template

Let P(n): "..."

Base:
   For n = n_0, ...
   So P(n_0) holds.

Inductive step:
   Let n ≥ n_0 be fixed.
   Assume P(n) (IH).
   Show P(n+1).
   [use IH]
   So P(n+1) holds.

Conclusion:
   By induction, P(n) holds for all n ≥ n_0.

Common mistakes

1. Forgetting the base case: no base, no induction.
2. Using a stronger property than $P(n)$ in the inductive step.
3. Not pointing out where IH is used: examiners want to see it.
4. Confusing “for all” and “for some”: in IH, $n$ is fixed.

Typical exam contexts

• Sums of integers, squares, powers
• Inequalities (e.g. $2^n \geq n + 1$)
• Recursive sequence formulas
• Divisibility (e.g. $4^n - 1$ divisible by 3)

?À toi de jouer

In an induction proof, the base case:

A.Checks the property for the smallest valueB.Assumes it holds for some nC.Proves P(n+1)D.Concludes

Valider