Mathematical induction

The prin­ci­ple of math­e­mat­i­cal in­duc­tion is a proof tech­nique in which a state­ment, \(P(n)\), is proven about a set of nat­u­ral num­bers \(n\). It may be best un­der­stood as treat­ing the state­ments like dom­i­noes: a state­ment \(P(n)\) is true if the \(n\)-th dom­ino is knocked down. We must knock down a first dom­ino, or prove that a base case \(P(m)\) is true. Next we must make sure the dom­i­noes are close enough to­gether to fall, or that the in­duc­tive 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 ex­am­ple to build our in­tu­ition be­fore giv­ing the proper defi­ni­tion of the prin­ci­ple. We’ll provide yet an­other proof that

$$ 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$$
for all in­te­gers \(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 ob­vi­ously) true, so we can move for­ward with the in­duc­tive step. The in­duc­tive step in­cludes an as­sump­tion, namely that the state­ment is true for some in­te­ger \(k\) that is larger than the base in­te­ger. For our ex­am­ple, if \(k\ge1\), we as­sume 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 as­sump­tion 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. Hope­fully the right-hand side will shake out to be the same. Get com­mon de­nom­i­na­tors so that the right-hand side of the above equa­tion is
$$\frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{(k+2)(k+1)}{2} = \frac{(k+1)([k+1]+1)}{2}.$$
There­fore,
$$ 1 + 2 + \cdots + k + (k+1) = \frac{(k+1)([k+1]+1)}{2}$$
as de­sired.

Let \(P(n)\) be the state­ment for \(n \ge 1\) that the sum of all in­te­gers be­tween 1 and \(n\) is \(n(n+1)/2\). At the be­gin­ning we showed that the base case, \(P(1)\), is true. Next we showed the in­duc­tive 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 in­te­gers \(n \ge 1\).

Defi­ni­tion for the nat­u­ral numbers

We are ready to prop­erly define math­e­mat­i­cal in­duc­tion.

Weak math­e­mat­i­cal induction

Let \(P(n)\) be a state­ment about the nat­u­ral num­bers. 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 math­e­mat­i­cal induction

Let \(P(n)\) be a state­ment about the nat­u­ral num­bers. 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 math­e­mat­i­cal in­duc­tion is a var­i­ant on math­e­mat­i­cal in­duc­tion by re­quiring a stronger in­duc­tive step, namely that the state­ment is true for all smaller in­dices, not just the im­me­di­ate pre­de­ces­sor.

In­duc­tion on a well-or­dered set

Well done if your im­me­di­ate re­sponse to the above ma­te­rial was, “Well, am I only re­stricted to this tech­nique on the nat­u­ral num­bers?” No. As long as your in­dex set is well-or­dered, then strong math­e­mat­i­cal in­duc­tion will work.

How­ever, if your or­dered set is not well-or­dered, you can prove prop­er­ties 1 and 2 above, and still not have it hold for all el­e­ments be­yond the base case. For in­stance, con­sider the set of non­nega­tive real num­bers, and let \(P(x)\) be the claim \(x\leq 1\). Then \(P(0)\) is true, and for all real num­bers \(x\ge 0\), \(P(x)\) is true when­ever \(P(y)\) is true for all \(0 \le y < x\). But of course \(P(2)\) is false.