AxiomProved

Principle of mathematical induction

Statement

Let $P(n)$ be a statement depending on a natural number $n \ge n_0$ . If (base case) $P(n_0)$ is true, and (inductive step) for every $k \ge n_0$ , $P(k)$ being true implies $P(k+1)$ is true, then $P(n)$ is true for every integer $n \ge n_0$ .

Why is it true?

Induction is climbing an infinite ladder: if you can reach the first rung, and from any rung you can always reach the next one, then you can reach every rung, no matter how high. You never need to check infinitely many rungs one by one — checking the first step and the 'next-step' mechanism is enough to cover them all at once.

Proof sketch

The principle follows from the well-ordering property of the natural numbers: every nonempty subset of $\{n_0, n_0+1, \dots\}$ has a least element. Suppose, for contradiction, that the set $S$ of integers $n \ge n_0$ for which $P(n)$ is false is nonempty; let $m$ be its least element. Since $P(n_0)$ is true, $m \ne n_0$ , so $m - 1 \ge n_0$ and $m-1 \notin S$ (as $m$ is least), i.e. $P(m-1)$ is true. By the inductive step, $P(m)$ must then be true, contradicting $m \in S$ . Hence $S$ is empty and $P(n)$ holds for all $n \ge n_0$ . (Equivalently, induction and well-ordering of $\mathbb{N}$ are interchangeable and both follow from the Peano axioms.)

Stated by

stated 1654Blaise Pascal

Topics that use this theorem

Mathematical Induction

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Kenneth H. Rosen (2012). Discrete Mathematics and Its Applications
George Pólya (1954). Induction and Analogy in Mathematics