Mathematical Induction

Proving Infinitely Many Cases at Once

Some statements must hold for every natural number — for instance $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ for all $n \ge 1$. Since there are infinitely many cases, mathematical induction proves them all with a finite argument. The intuition is a line of dominoes: if the first falls, and each falling domino knocks the next, then all fall.

An induction proof has two parts:

1. Base case — prove the statement for the smallest value (usually $n = 1$ or $n = 0$). This tips the first domino.
2. Inductive step — assume the statement holds for an arbitrary $n = k$ (the inductive hypothesis) and prove it then holds for $n = k + 1$. This shows each domino knocks the next.

Together these establish the statement for all $n$ at or above the base. Both parts are essential: the base case alone proves only one value, and the inductive step alone proves "if $k$ then $k+1$" but never gets the chain started — the dominoes could all be standing.

Strong induction is a variant whose inductive step may assume the statement for all values from the base up to $k$, not just $k$. This helps when a case depends on several earlier ones, as in proving every integer $> 1$ has a prime factorization. It is logically equivalent to ordinary induction but often more convenient.

Induction is the natural proof method for anything defined recursively, and it recurs throughout mathematics and computer science (where it proves the correctness of recursive algorithms). To prove $1 + 2 + \dots + n = \frac{n(n+1)}{2}$: the base case $n=1$ gives $1 = \frac{1 \cdot 2}{2}$; assuming it for $k$, adding $k+1$ to both sides yields the formula for $k+1$.

Common pitfall: omitting the base case or misusing the inductive hypothesis. Without a base case, the inductive step proves nothing — "if $k$ then $k+1$" never starts the chain, so all cases could be false. And the inductive step must use the assumption for $k$ to reach $k+1$; a step that ignores the hypothesis and re-proves $k+1$ from scratch is not a valid induction.