Mathematical Induction — Strong Form, Well-Ordering, Typical Proof Patterns

Mathematical induction proves a statement $P(n)$ is true for all natural numbers $n \geq n_0$.

Step 1 — Base case: Verify $P(n_0)$ is true (usually $n_0 = 1$).

Step 2 — Inductive hypothesis: Assume $P(k)$ is true for some arbitrary $k \geq n_0$.

Step 3 — Inductive step: Using the assumption, prove $P(k+1)$ is true.

If both steps succeed, $P(n)$ holds for all $n \geq n_0$.

graph TD
    A[Statement P of n to prove for all n] --> B[Step 1: Verify P of n0 - base case]
    B --> C{Is P of n0 true?}
    C -->|No| D[Statement is false, find counterexample]
    C -->|Yes| E[Step 2: Assume P of k true]
    E --> F[Step 3: Prove P of k+1 using P of k]
    F --> G{Can you derive P of k+1?}
    G -->|Yes| H[Done: P of n true for all n]
    G -->|No| I[Try strong induction or different approach]

In strong induction, instead of assuming only $P(k)$, we assume $P(n_0), P(n_0+1), \ldots, P(k)$ are ALL true. Then we prove $P(k+1)$.

Use strong induction when proving $P(k+1)$ needs more than just $P(k)$ — for example, when the recurrence depends on $P(k-1)$ or earlier terms.

Classic example: Proving every integer $n \geq 2$ can be written as a product of primes. To factor $n = a \times b$, we need both $a$ and $b$ (both less than $n$) to have prime factorisations — this requires the hypothesis for ALL values less than $n$, not just $n-1$.

Pattern 1 — Sum formulas: Prove $1 + 2 + \ldots + n = \frac{n(n+1)}{2}$. In the inductive step, add $(k+1)$ to both sides of $P(k)$.

Pattern 2 — Divisibility: Prove $n^3 - n$ is divisible by 6. Write $(k+1)^3 - (k+1) = (k^3 - k) + 3k(k+1)$ and show each part is divisible by 6.

Pattern 3 — Inequality: Prove $2^n > n$ for all $n \geq 1$. Use $2^{k+1} = 2 \cdot 2^k > 2k \geq k + 1$ (for $k \geq 1$).