A First Course in Linear Algebra

“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+\cdots +n={\displaystyle \frac{n(n+1)}{2}}$ for $n\ge 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\le n\le 40$ (check a few). However, when we check $n=41$ we find ${41}^2-41+41={41}^2\text{,}$ which is not prime.

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.

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.