# Mathematical induction

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

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.

Parents:

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

allof 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.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\).