Mathematical induction proves a statement for every natural number by showing that truth propagates from one case to the next.

To prove $P(n)$ for all $n\ge n_0$:

1. prove the base case $P(n_0)$;
2. assume $P(k)$ for an arbitrary $k\ge n_0$;
3. use that assumption to prove $P(k+1)$.

The assumption in step 2 is the induction hypothesis.

Why it works

The base case establishes the first link. The inductive step proves that every established link forces the next one, so the conclusion propagates through the natural numbers.

Strong induction

Sometimes the next case depends on several earlier cases. Strong induction assumes

$$P(n_0),P(n_0+1),\ldots,P(k)$$

when proving $P(k+1)$.

Ordinary and strong induction express the same underlying principle; the stronger-looking hypothesis is often simply more convenient.