# 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.

• I re­ally like this dom­ino anal­ogy.

Also, I’d ex­pect to see the word “all” some­where in this first para­graph—I think it’s worth em­pha­siz­ing the point that if we have the base case and the in­duc­tive step then the state­ment will be true for all of the num­bers af­ter the base case, just like all of the dom­i­noes af­ter the first one would fall down. I think the cur­rent fi­nal sen­tence of the in­tro para­graph doesn’t make this clear enough.

• I think it would be worth­while to ex­plic­itly call out that what’s hap­pen­ing here is that we’re re­plac­ing $$n$$ in the origi­nal equa­tion with $$k+1$$.