The principle of mathematical induction is a proof technique in which a statement, $P(n)$, 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 + \cdots + n = \frac{n(n+1)}{2}$$

for all integers $n \ge 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\ge1$, we assume that

$$1 + 2 + \cdots + k = \frac{k(k+1)}{2}$$

and try to prove that

$$ 1 + 2 + \cdots + k + (k+1) = \frac{(k+1)([k+1]+1)}{2}.$$

Take our assumption and add $k+1$ to both sides:

$$1+2+\cdots + 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 + \cdots + k + (k+1) = \frac{(k+1)([k+1]+1)}{2}$$

as desired.

Let $P(n)$ be the statement for $n \ge 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 \ge 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 \ge 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 \ge m$ if

$P(m)$ is true, and
For all $k \ge 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 \ge m$ if

$P(m)$ is true, and
For all $k \ge m$, $P(k)$ is true so long as $P(\ell)$ is true for all $m \le \ell < 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\ge 0$, $P(x)$ is true whenever $P(y)$ is true for all $0 \le y < x$. But of course $P(2)$ is false.

Eric Rogstad 17 Jul 2016 21:04 UTC
I really like this domino analogy.

Also, I’d expect to see the word “all” somewhere in this first paragraph—I think it’s worth emphasizing the point that if we have the base case and the inductive step then the statement will be true for all of the numbers after the base case, just like all of the dominoes after the first one would fall down. I think the current final sentence of the intro paragraph doesn’t make this clear enough.
Eric Rogstad 18 Jul 2016 1:29 UTC
I think it would be worthwhile to explicitly call out that what’s happening here is that we’re replacing $n$ in the original equation with $k+1$.

Mathematical induction

An example

Definition for the natural numbers

Weak mathematical induction

Strong mathematical induction

Induction on a well-ordered set