Mathematical induction

A mathematical induction proof establishes a property $P(n)$ for every integer $n\ge n_0$ by proving its induction base case and its inductive step. If a counterexample existed, the well-ordering principle would give a least one; its predecessor and the inductive implication exclude it. The starting case excludes a counterexample at $n_0$.

The useful idea is to cover infinitely many cases with two finite pieces of reasoning. The induction base case starts the chain, and the inductive step shows that success at an arbitrary stage propagates to the next. It is especially natural when a construction adds one item at a time: another row of a diagram, another input processed by an algorithm, or another term of a sequence. The loop invariant method is the same propagation idea applied to successive stages of a computation.

For the triangular number $T_n=1+2+\cdots +n$, the proposed formula is $T_n=n(n+1)/2$. At $n=1$, both sides are one. Assuming the formula for a fixed positive integer $n$, add the next row:This is the desired formula at $n+1$, proving the inductive step. For example, $T_5=15$ and $T_6=15+6=21$; these numerical cases illustrate the general step rather than replace it.

The second picture explains where the formula comes from: two copies of the triangular arrangement tile an $n$ by $n+1$ rectangle. Thus $2T_n=n(n+1)$. The mathematical induction argument certifies how the formula continues, while the rearrangement makes its factors visible. Neither picture is restricted to the five rows drawn: both constructions are specified for every positive integer $n$.