The many faces of mathematical induction

-

Let $\mathcal{P}(n)\backslash mathcal\{P\}(n)$ be a statement about a natural number n. To prove that it holds for every natural number, we proceed in two steps.

The first, the base case, consists of proving that $\mathcal{P}(0)\backslash mathcal\{P\}(0)$ is true.

The second, the inductive step, consists in showing that if $\mathcal{P}(n)\backslash mathcal\{P\}(n)$ is true for an arbitrary natural number n, then $\mathcal{P}(n+1)\backslash mathcal\{P\}(n\; +\; 1)$ is also true. This principle is often illustrated by a row of dominoes falling one after another once the first has been pushed over.

There are several refinements of this principle, though they remain equivalent to "simple induction." We can, of course, start the induction at a nonzero integer n₀, and conclude that $\mathcal{P}(n)\backslash mathcal\{P\}(n)$ is true for every integer n greater than or equal to n₀. We can also use "two-step induction": in this case, we prove that $\mathcal{P}(0)\backslash mathcal\{P\}(0)$ and $\mathcal{P}(1)\backslash mathcal\{P\}(1)$ are true, then that if $\mathcal{P}(n-1)\backslash mathcal\{P\}(n\; -\; 1)$ and $\mathcal{P}(n)\backslash mathcal\{P\}(n)$ are true, $\mathcal{P}(n+1)\backslash mathcal\{P\}(n\; +\; 1)$ is also true. We can even use "strong induction," in which, to show that $\mathcal{P}(n+1)\backslash mathcal\{P\}(n\; +\; 1)$ is true, we assume that the property holds in every preceding case.