Skip to main content

Proof Technique I Induction

“Induction” or “mathematical induction” is a framework for proving statements that are indexed by integers. In other words, suppose you have a statement to prove that is really multiple statements, one for \(n=1\text{,}\) another for \(n=2\text{,}\) a third for \(n=3\text{,}\) and so on. If there is enough similarity between the statements, then you can use a script (the framework) to prove them all at once.

For example, consider the theorem: \(1+2+3+\dots+n=\displaystyle\frac{n(n+1)}{2}\) for \(n\geq 1\text{.}\)

This is shorthand for the many statements \(1=\frac{1(1+1)}{2}\text{,}\) \(1+2=\frac{2(2+1)}{2}\text{,}\) \(1+2+3=\frac{3(3+1)}{2}\text{,}\) \(1+2+3+4=\frac{4(4+1)}{2}\text{,}\) and so on. Forever. You can do the calculations in each of these statements and verify that all four are true. We might not be surprised to learn that the fifth statement is true as well (go ahead and check). However, do we think the theorem is true for \(n=872\text{?}\) Or \(n=1,234,529\text{?}\)

To see that these questions are not so ridiculous, consider the following example from Rotman's Journey into Mathematics. The statement “\(n^{2}-n+41\) is prime” is true for integers \(1\leq n\leq 40\) (check a few). However, when we check \(n=41\) we find \(41^2-41+41=41^2\text{,}\) which is not prime.

So how do we prove infinitely many statements all at once? More formally, let us denote our statements as \(P(n)\text{.}\) Then, if we can prove the two assertions

  1. \(P(1)\) is true.
  2. If \(P(k)\) is true, then \(P(k+1)\) is true.

then it follows that \(P(n)\) is true for all \(n\geq 1\text{.}\) To understand this, I liken the process to climbing an infinitely long ladder with equally spaced rungs. Confronted with such a ladder, suppose I tell you that you are able to step up onto the first rung, and if you are on any particular rung, then you are capable of stepping up to the next rung. It follows that you can climb the ladder as far up as you wish. The first formal assertion above is akin to stepping onto the first rung, and the second formal assertion is akin to assuming that if you are on any one rung then you can always reach the next rung.

In practice, establishing that \(P(1)\) is true is called the “base case” and in most cases is straightforward. Establishing that \(P(k)\Rightarrow P(k+1)\) is referred to as the “induction step,” or in this book (and elsewhere) we will typically refer to the assumption of \(P(k)\) as the “induction hypothesis.” This is perhaps the most mysterious part of a proof by induction, since we are eventually trying to prove that \(P(n)\) is true and it appears we do this by assuming what we are trying to prove (when we assume \(P(k)\)). We are trying to prove the truth of \(P(n)\) (for all \(n\)), but in the induction step we establish the truth of an implication, \(P(k)\Rightarrow P(k+1)\text{,}\) an “if-then” statement. Sometimes it is even worse, since as you get more comfortable with induction, we often do not bother to use a different letter (\(k\)) for the index (\(n\)) in the induction step. Notice that the second formal assertion never says that \(P(k)\) is true, it simply says that if \(P(k)\) were true, what might logically follow. We can establish statements like “If I lived on the moon, then I could pole-vault over a bar 12 meters high.” This may be a true statement, but it does not say we live on the moon, and indeed we may never live there.

Enough generalities. Let us work an example and prove the theorem above about sums of integers. Formally, our statement is

\begin{equation*} P(n):\ 1+2+3+\dots+n=\frac{n(n+1)}{2}\text{.} \end{equation*}

A proof has two parts, a base case, which is usually easy, and an induction step that seems mysterious your first few times through.

Base Case.

\(P(1)\) is the statement \(1=\frac{1(1+1)}{2}\text{,}\) which we see simplifies to the true statement \(1=1\text{.}\) Done.

Induction Step.

We will assume \(P(k)\) is true, and will try to prove \(P(k+1)\text{.}\) Given what we want to accomplish, it is natural to begin by examining the sum of the first \(k+1\) integers.

\begin{align*} 1+2+3+\dots+(k+1) &=\left(1+2+3+\dots+k\right) + (k+1)\\ &=\frac{k(k+1)}{2} + (k+1)&&\text{Induction Hypothesis}\\ &=\frac{k^2+k}{2} + \frac{2k+2}{2}\\ &=\frac{k^2+3k+2}{2}\\ &=\frac{(k+1)(k+2)}{2}\\ &=\frac{(k+1)((k+1)+1)}{2} \end{align*}

We then recognize the two ends of this chain of equalities as \(P(k+1)\) and we have established the conclusion of the induction step (\(P(k+1)\)), by employing the hypothesis of the induction step (\(P(k)\)).

So, by mathematical induction, the theorem is true for all \(n\text{.}\)

How do you recognize when to use induction? The first clue is a statement that is really many statements, one for each integer. The second clue would be that you begin a more standard proof and you find yourself using words like “and so on” (like we did above!) or lots of ellipses (dots) to establish patterns that you are convinced continue on and on forever. However, there are many minor instances where induction might be warranted but we do not bother.

Induction is important enough, and used often enough, that it appears in various variations. The base case sometimes begins with \(n=0\text{,}\) or perhaps an integer greater than \(n=1\text{.}\) Some formulate the induction step as \(P(k-1)\Rightarrow P(k)\text{.}\) There is also a “strong form” of induction where we assume all of \(P(1)\text{,}\) \(P(2)\text{,}\) \(P(3)\text{,}\)… \(P(k)\) as a hypothesis for showing the conclusion \(P(k+1)\text{.}\)

You can find examples of induction in the proofs of Theorem GSP, Theorem DER, Theorem DT, Theorem DIM, Theorem EOMP, Theorem DCP, and Theorem UTMR.