The principle of mathematical induction is a proof technique in which a statement, , is proven about a set of natural numbers $n$ . It may be best understood as treating the statements like dominoes: a statement $P (n)$ is true if the $n$ -th domino is knocked down. We must knock down a first domino, or prove that a base case $P (m)$ is true. Next we must make sure the dominoes are close enough together to fall, or that the inductive step holds; in other words, we prove that if $k \geq m$ and $P (k)$ is true, $P (k + 1)$ is true. Then since $P (m)$ is true, $P (m + 1)$ is true; and since $P (m + 1)$ is true, $P (m + 2)$ is true, and so on.

An example

We'll do an example to build our intuition before giving the proper definition of the principle. We'll provide yet another proof that $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ for all integers $n \geq 1$ . First, let's check the base case, where $n = 1$ : $1 = \frac{1 (1 + 1)}{2} = \frac{2}{2} = 1.$ This is (fairly obviously) true, so we can move forward with the inductive step. The inductive step includes an assumption, namely that the statement is true for some integer $k$ that is larger than the base integer. For our example, if $k \geq 1$ , we assume that $1 + 2 + \dots + k = \frac{k (k + 1)}{2}$ and try to prove that $1 + 2 + \dots + k + (k + 1) = \frac{(k + 1) ([k + 1] + 1)}{2} .$ Take our assumption and add $k + 1$ to both sides: $1 + 2 + \dots + k + (k + 1) = \frac{k (k + 1)}{2} + k + 1.$ Now the left-hand sides of what we know and what we want are the same. Hopefully the right-hand side will shake out to be the same. Get common denominators so that the right-hand side of the above equation is $\frac{k (k + 1)}{2} + \frac{2 (k + 1)}{2} = \frac{(k + 2) (k + 1)}{2} = \frac{(k + 1) ([k + 1] + 1)}{2} .$ Therefore, $1 + 2 + \dots + k + (k + 1) = \frac{(k + 1) ([k + 1] + 1)}{2}$ as desired.

Let $P (n)$ be the statement for $n \geq 1$ that the sum of all integers between 1 and $n$ is $n (n + 1) / 2$ . At the beginning we showed that the base case, $P (1)$ , is true. Next we showed the inductive step, that if $k \geq 1$ and $P (k)$ is true, then $P (k + 1)$ is true. This means that since $P (1)$ is true, $P (2)$ is true; and since $P (2)$ is true, $P (3)$ is true; etc., so that $P (n)$ is true for all integers $n \geq 1$ .

Definition for the natural numbers

We are ready to properly define mathematical induction.

Weak mathematical induction

Let $P (n)$ be a statement about the natural numbers. Then $P$ is true for all $n \geq m$ if

$P (m)$ is true, and
For all $k \geq m$ , $P (k + 1)$ is true if $P (k)$ is.

Strong mathematical induction

Let $P (n)$ be a statement about the natural numbers. Then $P$ is true for all $n \geq m$ if

$P (m)$ is true, and
For all $k \geq m$ , $P (k)$ is true so long as $P (ℓ)$ is true for all $m \leq ℓ < k$ .

A note: strong mathematical induction is a variant on mathematical induction by requiring a stronger inductive step, namely that the statement is true for all smaller indices, not just the immediate predecessor.

Induction on a well-ordered set

Well done if your immediate response to the above material was, "Well, am I only restricted to this technique on the natural numbers?" No. As long as your index set is well-ordered, then strong mathematical induction will work.

However, if your ordered set is not well-ordered, you can prove properties 1 and 2 above, and still not have it hold for all elements beyond the base case. For instance, consider the set of nonnegative real numbers, and let $P (x)$ be the claim $x \leq 1$ . Then $P (0)$ is true, and for all real numbers $x \geq 0$ , $P (x)$ is true whenever $P (y)$ is true for all $0 \leq y < x$ . But of course $P (2)$ is false.

Mathematical induction