Mathematical Induction
Mathematical 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. Formally, to prove $P(n)$ for all $n \ge n_0$: prove the base case $P(n_0)$, then assume $P(k)$ (the inductive hypothesis) and prove $P(k+1)$. This 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, adding a limit case where $P$ holding for all $\beta < \lambda$ implies $P(\lambda)$.
Example
To prove the first $n$ positive integers sum to $n(n+1)/2$: the base case $n=1$ gives $1 = 1(2)/2 = 1$, and the inductive step assumes it holds for $k$, adds $(k+1)$ to both sides, and simplifies to show it holds for $k+1$. To prove $2^n > n$ for $n \ge 1$: base case $2^1 = 2 > 1$, and assuming $2^k > k$, then $2^{k+1} = 2 \cdot 2^k > 2k = k + k \ge k + 1$. Transfinite induction proves the Cantor-Bendixson theorem, that every closed subset of $\mathbb{R}$ is the union of a perfect set and a countable set, by proceeding through ordinal stages of removing isolated points.
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. Induction is deductive, not inductive reasoning, since you use a proven chain of implications rather than pattern-guessing; the name is historically unfortunate. 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.