A claim about every natural number cannot be checked case by case, because the cases never end. Induction replaces the endless checking with two finite jobs: show the claim at the first number, and show that whenever it holds at one number it holds at the next. Those two together reach every number, because any particular number is only finitely many steps from the start.

A line of dominoes falls when two things are true: the first one is pushed, and each one that falls knocks over its neighbour. Neither fact alone is enough. Knocking the first over with no chain does nothing, and a perfect chain with nobody pushing stays standing forever.

Two jobs cover the whole line: the claim at $1$, and the step from an arbitrary $n$ to $n+1$. Any particular natural number is reached from the base in finitely many steps, which is why nothing is left over.

Let $P(n)$ be a statement about natural numbers. If $P(1)$ holds, and if $P(n)\implies P(n+1)$ for every , then holds for every . The second job is an implication proved for an arbitrary : you assume — the inductive hypothesis — and derive from it. Assuming is not assuming what is to be proved, because what is to be proved is the implication, not itself.

• The base need not be $1$: starting at $n_0$ proves the claim for every $n\ge n_0$, and some claims are false below their base.

Do the two jobs. At the base the two sides are computed and compared. For the step, assume the formula at n — that is the inductive hypothesis, and it is the only thing about n you may use — then add the next term to both sides and rearrange the right-hand side until it is the same formula with n+1 in place of n. The rearrangement is ordinary algebra; the structure is what makes it a proof about every n.

Check the base case by computing both sides.

Assume the claim at an arbitrary n. This is the inductive hypothesis.

Add the next term to both sides, using the hypothesis on the left.

Put the right-hand side over one denominator and take out the common factor.

That is the formula with n+1 in place of n, so the step is proved and the principle applies.

The base case starts the chain; the step continues it. Neither on its own proves anything.

Sometimes the step needs more than the previous case. Assuming all the earlier cases at once is still valid, and proves the same kind of theorem.

• A proof by induction is a base case and a step, and both are needed.
• The step proves an implication, so assuming the claim at n is not circular.
• The base may be any starting point; the claim is then proved from there on.
• Strong induction assumes every earlier case and proves the same theorems.

Great work! You now know how to:

• Write a proof by induction with its base case and its step
• Say why assuming the claim at n is not circular
• Choose a base other than one when the claim fails below it
• Find the gap in an inductive argument whose step does not hold everywhere