# 9.3: Mathematical Induction

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

The Confusius is credited with the saying, "A journey of a thousand miles begins with a single step.'' In many ways, this is the central theme of this section. Here we introduce a method of proof, Mathematical Induction, which allows us to *prove* many of the formulas we have merely *motivated* in Sections 9.1 and 9.2 by starting with just a single step. A good example is the formula for arithmetic sequences we touted in Equation \ref{arithgeoformula}. Arithmetic sequences are defined recursively, starting with \(a_{1} = a\) and then \(a_{n+ 1} = a_{n} + d\) for \(n \geq 1\). This tells us that we start the sequence with \(a\) and we go from one term to the next by successively adding \(d\). In symbols,

\[ a, a+d, a+2d, a + 3d, a + 4d + \ldots\]

The pattern *suggested* here is that to reach the \(n\)th term, we start with \(a\) and add \(d\) to it exactly \(n-1\) times, which lead us to our formula \(a_{n} = a + (n-1)d\) for \(n \geq 1\). But how do we *prove* this to be the case? We have the following.

Note \(\PageIndex{1}\): The Principle of Mathematical Induction (PMI)

Suppose \(P(n)\) is a sentence involving the natural number \(n\).

**IF** \(P(1)\) is true and whenever \(P(k)\) is true, it follows that \(P(k+1)\) is also true

**THEN **the sentence \(P(n)\) is true for all natural numbers \(n\).

The Principle of Mathematical Induction, or PMI for short, is exactly that - a principle (another word for this you may have seen is 'axiom'). It is a property of the natural numbers we either choose to accept or reject. In English, it says that if we want to prove that a formula works for all natural numbers \(n\), we start by showing it is true for \(n=1\) (the '**base step**') and then show that if it is true for a generic natural number \(k\), it must be true for the next natural number, \(k+1\) (the '**inductive step**'). The notation \(P(n)\) acts just like function notation. For example, if \(P(n)\) is the sentence (formula) '\(n^2 + 1 = 3\)', then \(P(1)\) would be '\(1^2 + 1 = 3\)', which is false. The construction \(P(k+1)\) would be '\)(k+1)^2 + 1 = 3\)'. As usual, this new concept is best illustrated with an example. Returning to our quest to prove the formula for an arithmetic sequence, we first identify \(P(n)\) as the formula \(a_{n} = a + (n-1)d\).

To prove this formula is valid for all natural numbers \(n\), we need to do two things. First, we need to establish that \(P(1)\) is true. In other words, is it true that \(a_{1} = a + (1-1)d\)? The answer is yes, since this simplifies to \(a_{1} = a\), which is part of the definition of the arithmetic sequence. The second thing we need to show is that whenever \(P(k)\) is true, it follows that \(P(k+1)\) is true. In other words, we *assume* \(P(k)\) is true (this is called the 'induction hypothesis') and *deduce* that \(P(k+1)\) is also true. Assuming \(P(k)\) to be true seems to invite disaster - after all, isn't this essentially what we're trying to prove in the first place? To help explain this step a little better, we show how this works for specific values of \(n\). We've already established \(P(1)\) is true, and we now want to show that \(P(2)\) is true. Thus we need to show that \(a_{2} = a + (2-1)d\). Since \(P(1)\) is true, we have \(a_{1} = a\), and by the definition of an arithmetic sequence, \(a_{2}= a_{1} + d = a + d = a + (2-1)d\). So \(P(2)\) is true. We now use the fact that \(P(2)\) is true to show that \(P(3)\) is true. Using the fact that \(a_{2} = a + (2-1)d\), we show \(a_{3} = a + (3-1)d\). Since \(a_{3} = a_{2} + d\), we get \(a_{3}= (a + (2-1)d) + d = a + 2d = a+(3-1)d\), so we have shown \(P(3)\) is true. Similarly, we can use the fact that \(P(3)\) is true to show that \(P(4)\) is true, and so forth. In general, if \(P(k)\) is true (i.e., \(a_{k} = a + (k-1)d\)) we set out to show that \(P(k+1)\) is true (i.e., \(a_{k+ 1} = a + ((k+1)-1)d\)). Assuming \(a_{k} = a + (k-1)d\), we have by the definition of an arithmetic sequence that \(a_{k+ 1} = a_{k} + d\) so we get \(a_{k+ 1} = (a+(k-1)d) + d = a + kd = a + ((k+1)-1)d\). Hence, \(P(k+1)\) is true.

In essence, by showing that \(P(k+1)\) must always be true when \(P(k)\) is true, we are showing that the formula \(P(1)\) can be used to get the formula \(P(2)\), which in turn can be used to derive the formula \(P(3)\), which in turn can be used to establish the formula \(P(4)\), and so on. Thus as long as \(P(k)\) is true for some natural number \(k\), \(P(n)\) is true for all of the natural numbers \(n\) which follow \(k\). Coupling this with the fact \(P(1)\) is true, we have established \(P(k)\) is true for all natural numbers which follow \(n=1\), in other words, all natural numbers \(n\). One might liken Mathematical Induction to a repetitive process like climbing stairs (falling dominoes is the most widely used metaphor in the mainstream College Algebra books). If you are sure that (1) you can get on the stairs (the base case) and (2) you can climb from any one step to the next step (the inductive step), then presumably you can climb the entire staircase. We get some more practice with induction in the following example.

Example \(\PageIndex{1}\): Principle of Mathematical Induction

Prove the following assertions using the Principle of Mathematical Induction.

- The sum formula for arithmetic sequences: \(\displaystyle{\sum_{j=1}^{n} (a + (j-1)d) = \dfrac{n}{2}(2a + (n-1)d)}\).
- For a complex number \(z\), \(\left(\overline{z}\right)^n = \overline{z^{n}}\) for \(n \geq 1\).
- \(3^{n} > 100n\) for \(n > 5\).
- Let \(A\) be an \(n \times n\) matrix and let \(A'\) be the matrix obtained by replacing a row \(R\) of \(A\) with \(cR\) for some real number \(c\). Use the definition of determinant to show \(\det(A') = c \det(A)\).

**Solution**

- \item We set \(P(n)\) to be the equation we are asked to prove. For \(n=1\), we compare both sides of the equation given in \(P(n)\) \[ \begin{array}{rcl} \displaystyle{\sum_{j=1}^{1} (a + (j-1)d)} & \stackrel{\text{?}}{=} & \dfrac{1}{2}(2a + (1-1)d) \\ a + (1-1) d & \stackrel{\text{?}}{=} & \dfrac{1}{2} (2a) \\ a & = & a \, \checkmark \end{array} \] This shows the base case \(P(1)\) is true. Next we assume \(P(k)\) is true, that is, we assume \[ \displaystyle{\sum_{j=1}^{k} (a + (j-1)d) = \dfrac{k}{2}(2a + (k-1)d)}\] and attempt to use this to show \(P(k+1)\) is true. Namely, we must show \[ \displaystyle{\sum_{j=1}^{k+1} (a + (j-1)d) = \dfrac{k+1}{2}(2a + (k+1-1)d)}\] To see how we can use \(P(k)\) in this case to prove \(P(k+1)\), we note that the sum in \(P(k+1)\) is the sum of the first \(k+1\) terms of the sequence \(a_{k} = a + (k-1)d\) for \(k \geq 1\) while the sum in \(P(k)\) is the sum of the first \(k\) terms. We compare both side of the equation in \(P(k+1)\). \[\begin{array}{rcl} \underbrace{\displaystyle{\sum_{j=1}^{k+1} (a + (j-1)d)}}_{\text{summing the first \(k+1\) terms}} & \stackrel{\text{?}}{=} & \dfrac{k+1}{2}(2a + (k+1- 1)d) \\ && \\ \underbrace{\displaystyle{\sum_{j=1}^{k} (a + (j-1)d)}}_{\text{summing the first \(k\) terms}} + \underbrace{\vphantom{\displaystyle{\sum_{j=1}^{k+1}}}(a+(k+1-1)d)}_{\text{adding the (\)k+1\))st term}} & \stackrel{\text{?}}{=} & \dfrac{k+1}{2}(2a + kd) \\ && \\ \underbrace{\dfrac{k}{2}(2a + (k-1)d)}_{\text{Using \(P(k)\)}} + (a + kd) & \stackrel{\text{?}}{=} & \dfrac{(k+1)(2a+kd)}{2} \\ && \\ \dfrac{k(2a+(k-1)d) + 2(a + kd)}{2} & \stackrel{\text{?}}{=} & \dfrac{2ka+k^2d + 2a + kd}{2} \\ && \\ \dfrac{2ka + 2a + k^2d + kd}{2} & = & \dfrac{2ka + 2a + k^2d + kd}{2} \, \checkmark \\ \end{array} \] Since all of our steps on both sides of the string of equations are reversible, we conclude that the two sides of the equation are equivalent and hence, \(P(k+1)\) is true. By the Principle of Mathematical Induction, we have that \(P(n)\) is true for all natural numbers \(n\).
- We let \(P(n)\) be the formula \(\left(\overline{z}\right)^n = \overline{z^{n}}\). The base case \(P(1)\) is \(\left(\overline{z}\right)^1 = \overline{z^{1}}\), which reduces to \(\overline{z} = \overline{z}\) which is true. We now assume \(P(k)\) is true, that is, we assume \(\left(\overline{z}\right)^k = \overline{z^{k}}\) and attempt to show that \(P(k+1)\) is true. Since \(\left(\overline{z}\right)^{k+1} = \left(\overline{z}\right)^{k} \, \overline{z}\), we can use the induction hypothesis and write \(\left(\overline{z}\right)^k = \overline{z^{k}}\). Hence, \(\left(\overline{z}\right)^{k+1} = \left(\overline{z}\right)^{k} \, \overline{z} = \overline{z^{k}} \, \overline{z}\). We now use the product rule for conjugates\footnote{See Exercise \ref{zbarexercise} in Section \ref{ComplexZeros}.} to write \(\overline{z^{k}} \, \overline{z} = \overline{z^k z} = \overline{z^{k+1}}\). This establishes \(\left(\overline{z}\right)^{k+1} = \overline{z^{k+1}}\), so that \(P(k+1)\) is true. Hence, by the Principle of Mathematical Induction, \(\left(\overline{z}\right)^n = \overline{z^{n}}\) for all \(n \geq 1\).
- The first wrinkle we encounter in this problem is that we are asked to prove this formula for \(n > 5\) instead of \(n \geq 1\). Since \(n\) is a natural number, this means our base step occurs at \(n=6\). We can still use the PMI in this case, but our conclusion will be that the formula is valid for all \(n \geq 6\). We let \(P(n)\) be the inequality \(3^{n} > 100n\), and check that \(P(6)\) is true. Comparing \(3^6 = 729\) and \(100(6) = 600\), we see \(3^6 > 100(6)\) as required. Next, we assume that \(P(k)\) is true, that is we assume \(3^{k} > 100k\). We need to show that \(P(k+1)\) is true, that is, we need to show \(3^{k+1} > 100(k+1)\). Since \(3^{k+1} = 3 \cdot 3^{k}\), the induction hypothesis gives \(3^{k+1} = 3 \cdot 3^{k} > 3(100k) = 300k\). We are done if we can show \(300k > 100(k+1)\) for \(k \geq 6\). Solving \(300k > 100(k+1)\) we get \(k > \frac{1}{2}\). Since \(k \geq 6\), we know this is true. Putting all of this together, we have \(3^{k+1} = 3 \cdot 3^{k} > 3(100k) = 300k > 100(k+1)\), and hence \(P(k+1)\) is true. By induction, \(3^{n} > 100n\) for all \(n \geq 6\).
- \item To prove this determinant property, we use induction on \(n\), where we take \(P(n)\) to be that the property we wish to prove is true for all \(n \times n\) matrices. For the base case, we note that if \(A\) is a \(1 \times 1\) matrix, then \(A = [a]\) so \(A' = [ca]\). By definition, \(\det(A) = a\) and \(\det(A') = ca\) so we have \(\det(A') = c \det(A)\) as required. Now suppose that the property we wish to prove is true for all \(k \times k\) matrices. Let \(A\) be a \((k+1) \times (k+1)\) matrix. We have two cases, depending on whether or not the row \(R\) being replaced is the first row of \(A\).

Case 1: The row \(R\) being replaced is the first row of \(A\). By definition,

\[ \det(A') = \displaystyle{\sum_{p=1}^{n} a'_{1p} C'_{1p}}\]

where the \(1p\) cofactor of \(A'\) is \(C'_{1p} = (-1)^{(1+p)} \det\left(A'_{1p}\right)\) and \(A'_{1p}\) is the \(k \times k\) matrix obtained by deleting the \(1\)st row and \(p\)th column of \(A'\) (see Section 8.5 for a review of this notation). Since the first row of \(A'\) is \(c\) times the first row of \(A\), we have \(a'_{1p} = c \, a_{1p}\). In addition, since the remaining rows of \(A'\) are identical to those of \(A\), \(A'_{1p} = A_{1p}\). (To obtain these matrices, the first row of \(A'\) is removed.) Hence \(\det\left(A'_{1p}\right) = \det\left(A_{1p}\right)\), so that \(C'_{1p} = C_{1p}\). As a result, we get

\[ \det(A') = \displaystyle{\sum_{p=1}^{n} a'_{1p} C'_{1p}} = \displaystyle{\sum_{p=1}^{n} c \, a_{1p} C_{1p}} = c \displaystyle{\sum_{p=1}^{n} a_{1p} C_{1p}} = c \det(A), \]

as required. Hence, \(P(k+1)\) is true in this case, which means the result is true in this case for all natural numbers \(n \geq 1\). (You'll note that we did not use the induction hypothesis at all in this case. It is possible to restructure the proof so that induction is only used where it is needed. While mathematically more elegant, it is less intuitive, and we stand by our approach because of its pedagogical value.)

Case 2: The row \(R\) being replaced is the not the first row of \(A\). By definition,

\[ \det(A') = \displaystyle{\sum_{p=1}^{n} a'_{1p} C'_{1p}},\]

where in this case, \(a'_{1p} = a_{1p}\), since the first rows of \(A\) and \(A'\) are the same. The matrices \(A'_{1p}\) and \(A_{1p}\), on the other hand, are different but in a very predictable way \(-\) the row in \(A'_{1p}\) which corresponds to the row \(cR\) in \(A'\) is exactly \(c\) times the row in \(A_{1p}\) which corresponds to the row \(R\) in \(A\). In other words, \(A'_{1p}\) and \(A_{1p}\) are \(k \times k\) matrices which satisfy the induction hypothesis. Hence, we know \(\det\left(A'_{1p}\right) = c \det\left(A_{1p}\right)\) and \(C'_{1p} = c \, C_{1p}\). We get

\[ \det(A') = \displaystyle{\sum_{p=1}^{n} a'_{1p} C'_{1p}} = \displaystyle{\sum_{p=1}^{n} a_{1p} c\, C_{1p}} = c \displaystyle{\sum_{p=1}^{n} a_{1p} C_{1p}} = c \det(A), \]

which establishes \(P(k+1)\) to be true. Hence by induction, we have shown that the result holds in this case for \(n \geq 1\) and we are done.

While we have used the Principle of Mathematical Induction to prove some of the formulas we have merely motivated in the text, our main use of this result comes in Section 9.4 to prove the celebrated Binomial Theorem. The ardent Mathematics student will no doubt see the PMI in many courses yet to come. Sometimes it is explicitly stated and sometimes it remains hidden in the background. If ever you see a property stated as being true 'for all natural numbers \(n\)', it's a solid bet that the formal proof requires the Principle of Mathematical Induction.

### Contributors

- Carl Stitz, Ph.D. (Lakeland Community College) and Jeff Zeager, Ph.D. (Lorain County Community College)