Induction

Base case + inductive step — knock over a chain of dominoes.

The idea

Principle of mathematical induction. Let $P(n)$ be a statement about integers and let $n_0$ be an integer. If $P(n_0)$ is true, and if the truth of $P(k)$ implies the truth of $P(k+1)$ for every $k \geq n_0$, then $P(n)$ is true for every $n \geq n_0$.

The two hypotheses are called the base case and the inductive step, and the assumption of $P(k)$ made inside the step is the induction hypothesis. Assuming it is not circular reasoning: the step never claims that $P(k)$ is true, only that $P(k)$ would carry $P(k+1)$ along with it.

The conclusion follows because the base case gives $P(n_0)$, the step turns that into $P(n_0 + 1)$ and then into $P(n_0 + 2)$, and any particular $n \geq n_0$ is reached after finitely many applications. A row of dominoes falls for the same reason: one push, plus the guarantee that each domino topples the next.

The strength of the method is that the inductive step is a single argument covering infinitely many implications at once. Induction therefore suits statements built up one integer at a time — above all, identities claimed for every $n$.

Ways to work on it

• Walkthrough. Prove a closed-form sum formula by induction — base case, then inductive step.
• Practice. Prove a different sum formula by induction, start to finish.
• Hardest. Prove a sum formula whose inductive step needs heavier algebra.

Not sure where to start? Take the ten-question placement test.