12.C: Mathematical Induction

Suppose one is presented with the following sequence of equations:

\[\begin{align*} 1 &=1 \\ 1 + 3 &=4 \\ 1 + 3 + 5 &=9 \\ 1 + 3 + 5 + 7 &=16 \\ 1 + 3 + 5 + 7 + 9 &=25 \end{align*}\]

It is clear that there is a pattern. The numbers on the right side of the equations are the squares \(1^{2}\), \(2^{2}\), \(3^{2}\), \(4^{2}\), and \(5^{2}\) and, in the equation with \(n^{2}\) on the right side, the left side is the sum of the first \(n\) odd numbers. The odd numbers are

\[\begin{align*} 1 &= 2 \cdot 1 -1 \\ 3 &= 2 \cdot 2 -1 \\ 5 &= 2 \cdot 3 -1 \\ 7 &= 2 \cdot 4 -1 \\ 9 &= 2 \cdot 5 -1 \end{align*}\]

and from this it is clear that the \(n\)th odd number is \(2n - 1\). Hence, at least for \(n = 1\), \(2\), \(3\), \(4\), or \(5\), the following is true:

\[\label{eq:induction} 1 + 3 + \cdots + (2n-1) = n^2 \tag{\(S_n\)} \]

The question arises whether the statement \ref{eq:induction} is true for every \(n\). There is no hope of separately verifying all these statements because there are infinitely many of them. A more subtle approach is required. The idea is as follows: Suppose it is verified that the statement \(S_{n+1}\) will be true whenever \(S_{n}\) is true. That is, suppose we prove that, if \(S_{n}\) is true, then it necessarily follows that \(S_{n+1}\) is also true. Then, if we can show that \(S_{1}\) is true, it follows that \(S_{2}\) is true, and from this that \(S_{3}\) is true, hence that \(S_{4}\) is true, and so on and on. This is the principle of induction. To express it more compactly, it is useful to have a short way to express the assertion "If \(S_{n}\) is true, then \(S_{n+1}\) is true.'' As in Appendix B, we write this assertion as

\[ S_n \Rightarrow S_{n+1} \]

and read it as "\(S_{n}\) implies \(S_{n+1}\).'' We can now state the principle of mathematical induction.

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

Suppose \(S_{n}\) is a statement about the natural number \(n\) for each \(n = 1, 2, 3, \dots\). Suppose further that:

1. \(S_{1}\) is true.
2. \(S_{n} \Rightarrow S_{n+1}\) for every \(n \geq 1\). \end{enumerate} Then \(S_{n}\) is true for every \(n \geq 1\).

This is one of the most useful techniques in all of mathematics. It applies in a wide variety of situations, as the following examples illustrate.

Example \(\PageIndex{1}\)

Show that \(1 + 2 + \dots + n = \frac{1}{2}n(n + 1)\) for \(n \geq 1\).

Solution

Let \(S_{n}\) be the statement: \(1 + 2 + \dots + n = \frac{1}{2}n(n + 1)\) for \(n \geq 1\). We apply induction.

1. \(S_{1}\) is true. The statement \(S_{1}\) is \(1 = \frac{1}{2}1(1 + 1)\), which is true.
2. \(S_{n} \Rightarrow S_{n+1}\). We \textit{assume} that \(S_{n}\) is true for some \(n \geq 1\)---that is, that \[ 1+ 2 + \cdots + n = \frac{1}{2} n(n+1) \]

We must prove that the statement

\[ S_{n+1} : 1 + 2 + \cdots + (n+1) = \frac{1}{2} (n+1)(n+2) \]

is also true, and we are entitled to use \(S_{n}\) to do so. Now the left side of \(S_{n+1}\) is the sum of the first \(n + 1\) positive integers. Hence the second-to-last term is \(n\), so we can write

\[\begin{align*} 1 + 2 + \cdots + (n+1) & = (1 + 2+ \cdots + n)+(n+1) \\ &= \frac{1}{2} n(n+1) + (n+1) \quad \mbox{using } S_n \\ & = \frac{1}{2}(n+1)(n+2) \end{align*}\]

This shows that \(S_{n+1}\) is true and so completes the induction. \end{solution} \end{example}

In the verification that \(S_{n} \Rightarrow S_{n+1}\), we assume that \(S_{n}\) is true and use it to deduce that \(S_{n+1}\) is true. The assumption that \(S_{n}\) is true is sometimes called the induction hypothesis.

Example \(\PageIndex{2}\)

If \(x\) is any number such that \(x \neq 1\), show that \(1 + x + x^2 + \cdots + x^n = \frac{x^{n+1}-1}{x-1}\) for \(n \geq 1\).

Solution

Let \(S_{n}\) be the statement: \(1 + x + x^2 + \cdots + x^n = \frac{x^{n+1}-1}{x-1}\).

1. \(S_{1}\) is true. \(S_{1}\) reads \( 1+x = \frac{x^2 -1}{x-1}\), which is true because \(x^{2} - 1 = (x - 1)(x + 1)\).
2. \(S_{n} \Rightarrow S_{n+1}\). Assume the truth of \(S_{n}\) : \(1 + x + x^{2} + \dots + x^n = \frac{x^{n+1}-1}{x-1}\).

We must \textit{deduce} from this the truth of \(S_{n+1}\): \(1 + x + x^{2} + \cdot + x^{n+1} = \frac{x^{n+2}-1}{x-1}\). Starting with the left side of \(S_{n+1}\) and using the induction hypothesis, we find

\[\begin{align*} 1 +x + x^2 + \cdots + x^{n+1} & = (1 + x + x^2 + \cdots + x^n) + x^{n+1} \\ &= \frac{x^{n+1} -1 }{x-1} + x^{n+1} \\ &= \frac{x^{n+1} -1 + x^{n+1}(x-1)}{x-1} \\ &= \frac{x^{n+2}-1}{x-1} \end{align*}\]

This shows that \(S_{n+1}\) is true and so completes the induction.

Both of these examples involve formulas for a certain sum, and it is often convenient to use summation notation. For example, \( \sum_{k=1}^{n} (2k-1)\) means that in the expression \((2k - 1)\), \(k\) is to be given the values \(k = 1, k = 2, k = 3, \dots , k = n\), and then the resulting \(n\) numbers are to be added. The same thing applies to other expressions involving \(k\). For example,

\[\begin{align*} \sum_{k=1}^{n} k^3 &=1^3 + 2^3 + \cdots + n^3 \\ \sum_{k=1}^{5} (3k-1) &= (3 \cdot 1 -1) + (3 \cdot 2 - 1) + (3 \cdot 3 - 1) +(3 \cdot 4 - 1) + (3 \cdot 5 - 1) \end{align*}\]

The next example involves this notation.

Example \(\PageIndex{1}\)

Show that \(\sum_{k=1}^{n} (3k^2-k) = n^2(n+1)\) for each \(n \geq 1\).

Solution

Let \(S_{n}\) be the statement: \(\sum_{k=1}^{n} (3k^2-k) = n^2(n+1)\). \

1. \(S_{1}\) is true. \(S_{1}\) reads \((3 \cdot 1^2 - 1) = 1^{2}(1 + 1)\), which is true.
2. \(S_{n} \Rightarrow S_{n+1}\). Assume that \(S_{n}\) is true. We must prove \(S_{n+1}\):

\[\begin{align*} \sum_{k=1}^{n+1} (3k^2-k) &= \sum_{k=1}^{n}(3k^2-k) + [3(n+1)^2 - (n+1)] \\ & = n^2(n+1)+(n+1)[3(n+1)-1] \tag{using \(S_n\)} \\ & = (n+1)[n^2 + 3n+2]\\ & = (n+1)[(n+1)(n+2)] \\ & = (n+1)^2(n+2) \end{align*}\]

This proves that \(S_{n+1}\) is true.

We now turn to examples wherein induction is used to prove propositions that do not involve sums.

Example \(\PageIndex{1}\)

Show that \(7^n + 2\) is a multiple of \(3\) for all \(n \geq 1\).

Solution

1. \(S_{1}\) is true: \(7^1 + 2 = 9\) is a multiple of \(3\).
2. \(S_{n} \Rightarrow S_{n+1}\). Assume that \(7^n + 2\) is a multiple of \(3\) for some \(n \geq 1\); say, \(7^n + 2 = 3m\) for some integer \(m\). Then \[ 7^{n+1} +2 = 7(7^n) +2 = 7(3m-2)+2 = 21m-12 = 3(7m-4) \]

so \(7^{n+1} + 2\) is also a multiple of \(3\). This proves that \(S_{n+1}\) is true.

In all the foregoing examples, we have used the principle of induction starting at \(1\); that is, we have verified that \(S_{1}\) is true and that \(S_{n} \Rightarrow S_{n+1}\) for each \(n \geq 1\), and then we have concluded that \(S_{n}\) is true for every \(n \geq 1\). But there is nothing special about \(1\) here. If \(m\) is some fixed integer and we verify that

1. \(S_{m}\) is true.
2. \(S_{n} \Rightarrow S_{n+1}\) for every \(n \geq m\).

then it follows that \(S_{n}\) is true for every \(n \geq m\). This "extended'' induction principle is just as plausible as the induction principle and can, in fact, be proved by induction. The next example will illustrate it. Recall that if \(n\) is a positive integer, the number \(n!\) (which is read "\(n\)-factorial'') is the product

\[ n! = n(n-1)(n-2)\cdots 3 \cdot 2 \cdot 1 \]

of all the numbers from \(n\) to \(1\). Thus \(2! = 2\), \(3! = 6\), and so on.

Example \(\PageIndex{5}\)

Show that \(2^n < n!\) for all \(n \geq 4\).

Solution

Observe that \(2^n < n!\) is actually false if \(n = 1, 2, 3\).

1. \(S_{4}\) is true. \(2^4 = 16 < 24 = 4!\).
2. \(S_{n} \Rightarrow S_{n+1}\) if \(n \geq 4\). Assume that \(S_{n}\) is true; that is, \(2^n < n!\). Then \[ \begin{aligned}
   2^{n+1} & =2 \cdot 2^n \\
   & <2 \cdot n!\quad \text { because } 2^n<n! \\
   & <(n+1) n!\quad \text { because } 2<n+1 \\
   & =(n+1)!
   \end{aligned}\]

Hence \(S_{n+1}\) is true.