Mathematical induction

Summary

Mathematical induction is a method to prove that a property $P(n)$ holds for every natural number $n$. A proof by induction has two steps. The base case proves $P(0)$. The induction step proves, for an arbitrary natural number $n$, that $P(n)$ implies $P(n + 1)$. Then $P(n)$ holds for every natural number $n$.

Remarks

The method is valid because of the induction axiom of the Peano axioms. In the induction step, the assumption $P(n)$ is the induction hypothesis. Common variants are induction from an arbitrary base case and strong induction.

Explanations

L1 human

Think of a line of dominoes that never ends. If the first domino falls, and each falling domino knocks over the next one, then every domino falls. The base case is the first domino, and the induction step is the rule that each domino knocks over the next one.