Induction

Definition

Induction proves that a property $P(n)$P(n) holds for every integer from a rank $n_0$n0​ onwards, by means of two checks only:

These two points establish infinitely many statements. That is their power: one only ever checks a single case and a single implication.

An image, and its limit

A row of dominoes: knocking the first over, and guaranteeing that each topples the next, suffices to bring them all down.

The image is right about the mechanism and wrong about the reach. A row of dominoes is finite and the falling takes time; induction bears on infinitely many ranks and does not unfold. It does not narrate a propagation, it proves a property.

A worked example

Let us show that the sum of the first $n$n integers is $\dfrac{n(n+1)}{2}$2n(n+1)​.

Base case. For $n = 1$n=1: the sum is 1, and $\dfrac{1 \times 2}{2} = 1$21×2​=1.

Inductive step. Suppose the formula holds at rank $n$n. Then:

$1 + 2 + \dots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$1+2+⋯+n+(n+1)=2n(n+1)​+(n+1)=2n(n+1)+2(n+1)​=2(n+1)(n+2)​

That is the formula at rank $n+1$n+1. Both steps hold, so the property is true for every $n \geq 1$n≥1.

Both steps are necessary

The inductive step alone proves nothing. Take $P(n)$P(n): "$n = n + 1$n=n+1".

This property is hereditary: if $n = n+1$n=n+1, then adding 1 to both sides gives $n + 1 = n + 2$n+1=n+2. The step propagates perfectly — and the property is false for every integer, because no rank ever starts it.

The base case alone is no better: a property can be true at 1 and false thereafter.

Strong induction

Some proofs need more than the previous rank. Strong induction assumes $P(k)$P(k) for all $k \leq n$k≤n, and not for $n$n alone.

It serves when the step calls on a much earlier rank — decomposing an integer into prime factors, for instance, refers to two arbitrary smaller factors, not to the predecessor.

Summary

A starting point and a propagating step prove infinitely many cases; neither can be dispensed with.