Mathematical Induction

The Domino Principle

Many statements must hold for every natural number — "the sum $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ for all $n$." You cannot check infinitely many cases, so mathematical induction proves them all at once. The image is a line of dominoes: if the first falls, and each falling domino knocks the next, then all fall.

Induction has two parts:

1. Base case — prove the statement for the smallest value (usually $n = 1$ or $n = 0$). This is knocking over 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 is showing each domino knocks the next.

Together they establish the statement for all $n \ge$ the base. Neither part alone is enough: the base case without the step proves only one value; the step without the base proves nothing (the dominoes might all be standing, with none pushed).

Strong induction is a variant where the inductive step may assume the statement for all values up to $k$ (not just $k$) — useful when a case depends on several smaller ones, as in proving every integer $> 1$ has a prime factorization. It is logically equivalent to ordinary induction but often more convenient.

Induction is not just a proof tool; it mirrors recursion in programming — a base case plus a step that reduces to a smaller instance is exactly how recursive functions terminate and how their correctness is proved.

Common pitfall: forgetting the base case, or misusing the inductive hypothesis. Without the base case, the inductive step proves nothing — you have shown "if $k$ then $k+1$" but never started the chain. And the inductive step must use the assumption for $k$ to establish $k+1$; a step that re-proves $k+1$ from scratch, ignoring the hypothesis, is not an induction (and usually is circular).