Mathematical Induction
Calculus & Advanced MathMathematical induction is a proof technique for statements about all natural numbers, working by proving a base case and an inductive step.
Formula
\text{Prove } P(1); \text{ prove } P(k) \text{ implies } P(k+1)
Definition
Mathematical induction is a proof method for showing something is true for every natural number. It has two steps: show it is true for the first case, then show that if it is true for one number, it must be true for the next.
Example
Prove the first $n$ positive integers sum to $n(n+1)/2$. Base case: $n=1$: $1 = 1(2)/2 = 1$. True. Inductive step: assume it holds for $k$; add $(k+1)$ to both sides and simplify to show it holds for $k+1$.
Key Insight
Think of dominoes: prove the first falls (base case), and prove each falling domino knocks down the next (inductive step). Then all dominoes fall.
Definition
To prove $P(n)$ for all $n \ge n_0$: (1) Base case: prove $P(n_0)$. (2) Inductive step: assume $P(k)$ is true (inductive hypothesis) and prove $P(k+1)$. Conclusion: $P(n)$ holds for all $n \ge n_0$. Strong induction assumes $P$ holds for all values up to $k$.
Example
Prove $2^n > n$ for all $n \ge 1$. Base: $2^1 = 2 > 1$. Inductive step: assume $2^k > k$. Then $2^{k+1} = 2 \cdot 2^k > 2k = k + k \ge k + 1$ (for $k \ge 1$). QED.
Key Insight
Induction is deductive, not inductive reasoning: you use a proven chain of implications, not pattern-guessing. The name is historically unfortunate.
Definition
Mathematical induction is equivalent to the well-ordering principle of $\mathbb{N}$ (every non-empty subset has a least element) and to Peano's fifth axiom. Transfinite induction extends the technique to ordinals: prove the base case, successor case ($\alpha$ implies $\alpha+1$), and limit case ($P$ holds for all $\beta < \lambda$ implies $P(\lambda)$).
Example
Transfinite induction proves the Cantor-Bendixson theorem: every closed subset of $\mathbb{R}$ is the union of a perfect set and a countable set. The proof proceeds through ordinal stages of removing isolated points.
Key Insight
Structural induction in computer science proves properties of recursive data structures (trees, lists) using the same principle applied to the recursive structure rather than to natural numbers.