7.3: Mathematical Induction

Math 370 Learning Objectives

• Use the Principle of Mathematical Induction to prove algebraic identities.

The Chinese philosopher Confucius 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 7.1 and 7.2 by starting with just a single step. A good example is the formula for arithmetic sequences we touted in Theorem 7.1.1.

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\nonumber\]

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.

The Principle of Mathematical Induction (PMI)

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

IF

1. \(P(1)\) is true and
2. 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.¹ 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+k d=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.² 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} \)

Prove the following assertions using the Principle of Mathematical Induction. Unless otherwise noted, \( n \) is a natural number.

1. The sum formula for arithmetic sequences: \(\displaystyle{\sum_{j=1}^{n} (a + (j-1)d) = \frac{n}{2}(2a + (n-1)d)}\).
2. For a complex number \( z \), \( \left( \overline{z} \right)^n = \overline{z^{n}} \), where \( n \ge 1 \).
3. \( 1^3 + 2^3 + 3^3 + \cdots + n^3 = \frac{n^2 (n + 1)^2}{4} \)
4. \(3^{n} \gt 100n\) for \(n \gt 5\).
5. \( n^2 + n \) is divisible by \(2\).

Solution

1. 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}\nonumber\]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)}\nonumber\]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)}\nonumber\]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}\nonumber\]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\).
2. Let \(P(n)\) be the formula \(\left(\overline{z}\right)^n = \overline{z^{n}}\).
   1. For \( n = 1 \), we have \(\left(\overline{z}\right)^1 = \overline{z} = \overline{z^1} \). Thus, \( P(1) \) is true.
   2. [Induction Hypothesis] Assume \( P(k) \) is true. That is, assume \(\left(\overline{z}\right)^k = \overline{z^{k}}\).
   3. To show \( P(k + 1) \) is true, we need to show that \(\left(\overline{z}\right)^{k + 1} = \overline{z^{k + 1}}\).\[ \begin{array}{rclr} \left(\overline{z}\right)^{k+1} & = & \left(\overline{z}\right)^{k} \, \overline{z} & \\
      & = & \overline{z^k} \, \overline{z} & \left( \text{Induction Hypothesis} \right) \\ 
      & = & \overline{z^k z} & \left( \text{Product Rule for Conjugates} \right) \\
      & = & \overline{z^{k+1}} & \\
      \end{array} \nonumber \]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\).
3. Let \(P(n)\) be the formula \( 1^3 + 2^3 + 3^3 + \cdots + n^3 = \dfrac{n^2 (n + 1)^2}{4} \).
   1. For \( n = 1 \), we have \(1^3 = \dfrac{1^2 (1 + 1)^2}{4}\). Thus, \( P(1) \) is true.
   2. [Induction Hypothesis] Assume \( P(k) \) is true. That is, assume \( 1^3 + 2^3 + 3^3 + \cdots + k^3 = \frac{k^2 (k + 1)^2}{4} \).
   3. To show \( P(k + 1) \) is true, we need to show that \( 1^3 + 2^3 + 3^3 + \cdots + k^3 + (k + 1)^3 = \frac{(k + 1)^2 (k + 1 + 1)^2}{4} = \frac{(k + 1)^2(k + 2)^2}{4}\).\[ \begin{array}{rclr}
      1^3 + 2^3 + 3^3 + \ldots + k^3 + (k + 1)^3 & = & \left( 1^3 + 2^3 + 3^3 + \ldots + k^3 \right) + (k + 1)^3 &  \\
      & = & \dfrac{k^2 (k + 1)^2}{4} + (k + 1)^3 & \left( \text{Induction Hypothesis} \right) \\
      & = & \dfrac{k^2 (k + 1)^2 + 4(k + 1)^3}{4} & \\
      & = & \dfrac{(k + 1)^2 \left(k^2 + 4 (k + 1) \right)}{4} & \\
      & = & \dfrac{(k + 1)^2 \left(k^2 + 4 k + 4 \right)}{4} & \\
      & = & \dfrac{(k + 1)^2 (k + 2)^2}{4} & \\
      \end{array} \nonumber \]Therefore,  \( 1^3 + 2^3 + 3^3 + \cdots + k^3 + (k + 1)^3 = \frac{(k + 1)^2 (k + 1 + 1)^2}{4} = \frac{(k + 1)^2(k + 2)^2}{4}\), and so \(P(k+1)\) is true. Hence, by the Principle of Mathematical Induction, \( 1^3 + 2^3 + 3^3 + \cdots + n^3 = \frac{n^2 (n + 1)^2}{4} \) for all natural numbers \( n \).
4. 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\).
   Let \(P(n)\) be the inequality \(3^{n} > 100n\).
   1. For \( n = 6 \), we have \(3^6 = 729 \gt 600 = 100(6) \). Thus, \( P(6) \) is true.
   2. [Induction Hypothesis] Assume \( P(k) \) is true. That is, assume \(3^{k} > 100k\).
   3. To show \( P(k + 1) \) is true, we need to show \(3^{k+1} \gt 100(k+1) = 100k + 100\).\[ \begin{array}{rclr}
      3^{k + 1} & = & 3^k \cdot 3 & \\
       & \gt & 100k \cdot 3 & \left( \text{Induction Hypothesis} \right) \\
       & = & 100k + 200 k & \left( \text{our goal is to get to }100k + 100\text{, so isolating }100k\text{ is helpful} \right) \\
       & \gt & 100k + 100 & \left( 200k \gt 100 \text{ when } k \gt \frac{1}{2}\text{. Since }k \ge 6\text{, }200k \gt 100 \right) \\
      \end{array} \nonumber \]Hence \(P(k+1)\) is true. By induction, \(3^{n} > 100n\) for all \(n \geq 6\).
5. Let \( (P(n) \) be the statement that \( n^2 +  n \) is divisible by \( 2 \).
   1. For \( n = 1 \), we have \( 1^1 + 1 = 2 \). This is definitely divisible by \( 2 \) (since \( \frac{2}{2} = 1 \)), so \( P(1) \) is true
   2. [Induction Hypothesis] Assume \( P(k) \) is true. That is, assume \( k^2 + k \) is divisible by \( 2 \).
   3. To show \( P(k + 1) \) is true, we need to show that \( (k + 1)^2 + (k + 1) \) is divisible by \( 2 \).\[ \begin{array}{rclr}
      (k + 1)^2 + (k + 1) & = & k^2 + 2k + 1 + k + 1 & \\
       & = & (k^2 + k) + 2k + 1 + 1 & \left( \text{Associative and Commutative Properties of Addition}^{\text{3}} \right) \\
       & = & (k^2 + k) + 2k + 2 &  \\
       & = & (k^2 + k) + 2(k + 1) & \\
      \end{array} \nonumber \]We know that \( k^2 + k \) is divisible by \( 2 \), by the Induction Hypothesis. We also know that \( 2(k + 1) \) is divisible by \( 2 \). The sum of numbers divisible by \( 2 \) is also divisible by \( 2 \),^d so \( (k + 1)^2 + (k + 1) \) must be divisible by \( 2 \). Hence, \( P(k + 1) \) is true. Thus, the claim is true for all natural numbers \( n \) by Mathematical Induction.

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

Section Footnotes

¹ Another word for this you may have seen is "axiom."

² Falling dominoes is the most widely used metaphor in the mainstream College Algebra books.

³ The reason for this step is to group \( k^2 + k \) together so we can use the Induction Hypothesis.