= Mathematical induction
{title2=$P(n_0),\quad P(n)\Rightarrow P(n+1)$}
{wiki}
= Induction
{synonym}
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:
$$
T_{n+1}=T_n+(n+1)=\frac{n(n+1)}2+(n+1)=\frac{(n+1)(n+2)}2.
$$
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.
\Image[/induction-triangular-number.png]
{title=Adding the next row gives the induction step; rearranging two triangular arrays gives the same formula geometrically}
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$.
Back to article page
