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

1. $~$P(m)$~$ is true, and
2. 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

1. $~$P(m)$~$ is true, and
2. 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.