Skip to main content

Section 6.2 Basic induction

Suppose we want to show that \(n!\) is at least \(2^n-2\text{,}\) for every \(n \ge 1\) (where \(n\) must be an integer). We could start verifying this fact for each of the possible values for \(n\text{:}\)

\begin{align*} 1!\amp= 1 \amp 2^1-2 \amp= 0 \amp 1 \amp \ge 0 \ \checkmark \\ 2!\amp= 2 \amp 2^2-2 \amp=2 \amp 2 \amp \ge 2 \ \checkmark\\ 3!\amp= 6 \amp 2^3 -2\amp=6 \amp 6 \amp\ge 6 \ \checkmark\\ 4!\amp= 24 \amp 2^4-2\amp=14\amp 24 \amp\ge 14 \ \checkmark \end{align*}

We could continue verifying the values one at a time, but the process would go on forever, so we'd never be able to complete the proof.

Instead, think about the following method. Let's suppose that the inequality holds for some value \(n=k-1\text{,}\) i.e. that

\begin{equation*} (k-1)!\ge 2^{k-1}-2\text{.} \end{equation*}

Now let's use the fact that we can easily calculate \(k!\) from \((k-1)!\) together with our supposition, to deduce that the inequality holds when \(n=k\text{,}\) i.e. that

\begin{equation*} k! \ge 2^{k}-2\text{.} \end{equation*}

This is enough to prove the inequality for every integer \(n \ge 1\text{.}\) For example, if we wanted to be sure that the inequality holds for \(n=100\text{,}\) we could take the fact that we know it holds for \(1\text{,}\) to deduce that it holds for \(2\text{,}\) then the fact that it holds for \(2\) allows us to deduce that it holds for \(3\text{.}\) By repeating this \(97\) more times, eventually we see that since it holds for \(99\text{,}\) we can deduce that it holds for \(100\text{.}\)

Definition 6.2.2.

In a proof by induction, determining that \(P(n_0)\) is true for some particular integer \(n_0\) is called the base case. Proving that \(P(k-1) \Rightarrow P(k)\) for each \(k > n_0\) is called the induction step. The assumption we make in the induction step, that \(P(k-1)\) is true for some arbitrary \(k > n_0\text{,}\) is called the induction hypothesis.

Now that we've gone through the formalities, let's write a proper proof by induction for the inequality we used to introduce this idea.

Prove by induction that \(n!\ge 2^n-2\text{,}\) for every integer \(n \ge 2\text{.}\) (This inequality is actually true for every \(n \ge 0\text{,}\) but the proof is simpler if we restrict our attention to \(n \ge 2\text{.}\))

Proof

Base case: \(n=2\text{.}\) We have \(n!=2!=2\text{,}\) and

\begin{equation*} 2^n-2=2^2-2=4-2=2\text{.} \end{equation*}

Certainly \(2 \ge 2\text{,}\) so the inequality holds for \(n=2\text{.}\) This completes the proof of the base case.

Induction step: We begin with the induction hypothesis. Let \(k > 2\) be arbitrary, and suppose that the inequality holds for \(n=k-1\text{;}\) that is, assume that \((k-1)! \ge 2^{k-1}-2\text{.}\) Then

\begin{align*} k! & = k \cdot (k-1)! \\ & \ge k \cdot (2^{k-1}-2) && \text{(Induction hypothesis)} \\ & \ge 3 \cdot (2^{k-1}-2) && \text{($k > 2$, so $k \ge 3$)} \\ & = 2 \cdot 2^{k-1} + (2^{k-1} -6) \\ & \ge 2 \cdot 2^{k-1} + (2^2 -6) && \text{($k > 2$, so $k - 1 \ge 2$)} \\ & = 2^{k} - 2 . \end{align*}

This is what we wanted to establish, so we have completed the proof of the induction step.

By the Principle of Mathematical Induction, \(n! \ge 2^n-2\) for every integer \(n \ge 2\text{.}\)

Proofs by induction work very naturally with recursively-defined sequences, since the recurrence relation gives us information about the \(k^{\text{th}}\) term of the sequence, based on previous terms.

Consider the sum of the first \(n\) integers. We can think about this as a recursively-defined sequence, by defining \(s_1=1\text{,}\) and \(s_{n}=s_{n-1}+n\text{,}\) for every \(n \ge 2\text{.}\) Thus,

\begin{align*} s_2&=1+2, & s_3&=s_2+3=1+2+3, &&\text{etc.} \end{align*}

Prove by induction that \(s_n=n(n+1)/2\text{,}\) for every \(n \ge 1\text{.}\)

Proof

Base case: \(n=1\text{.}\) We have \(s_n=s_1=1\text{,}\) and

\begin{equation*} n(n+1)/2=1(1 + 1)/2=1\text{,} \end{equation*}

so the equality holds for \(n=1\text{.}\) This completes the proof of the base case.

Induction step: We begin with the induction hypothesis. Let \(k > 1\) be arbitrary, and suppose that the equality holds for \(n=k -1\text{;}\) that is, assume that

\begin{equation*} s_{k-1}=\frac{\bigl( k-1) \bigl( (k-1) +1\bigr)}{2} . \end{equation*}

Now, we have

\begin{align*} s_k & = s_{k-1} + k && \text{(definition of $s_k$)} \\ & = \frac{\bigl( k-1 \bigr) \bigl( (k-1) +1\bigr)}{2} + k && \text{(induction hypothesis)} \\ & = \frac{(k-1) (k)}{2} + \frac{2k}{2} \\ & = \frac{k \bigl( (k-1) + 2)}{2} && \text{(factor out $k/2$)} \\ & = \frac{k (k + 1)}{2} . \end{align*}

This completes the proof of the induction step.

By the Principle of Mathematical Induction, \(s_n=n(n+1)/2\) for every \(n \ge 1\text{.}\)

Caution: the steps of a proof by induction are precisely defined, and if you leave any of them out, or forget the conditions required, things can go badly wrong. The base case may seem obvious, but can't be left out; also, the hypothesis that \(k > n_0\) may be critical to the proof, as we saw in Example 6.2.3.

Let's look at an example where, by forgetting to include the base case, we can give a “proof by induction” of something that is clearly false.

Here is a “proof by induction” (without a base case) that every integer \(n\) is at least \(1000\text{.}\)

Proof by induction

Induction step: We begin with the induction hypothesis. Let \(k\) be arbitrary, and suppose that \(k -1 \ge 1000\text{.}\)

Now we want to deduce that \(k \ge 1000\text{.}\) But clearly,

\begin{equation*} k \ge k - 1 \ge 1000 \end{equation*}

(by our induction hypothesis), which is what we wanted to deduce. This completes the proof of the induction step.

By the Principle of Mathematical Induction, \(n \ge 1000\) for every integer \(n\text{.}\)

Now it's your turn to try a few. Don't leave out any of the steps! (Take a look at your Math 2000 textbook if you want more examples.)

Use the Principle of Mathematical Induction to prove the following:

  1. For the recursively-defined sequence given by \(b_1=5\) and \(b_n=b_{n-1}+4\) for all \(n \ge 2\text{,}\) prove that for every integer \(n \ge 1\text{,}\) \(b_n=5+4(n-1)\text{.}\)

  2. For the recursively-defined sequence given by \(c_1=3\) and \(c_n=c_{n-1}+3 \cdot 2^{n-1}\) for all \(n \ge 2\text{,}\) prove that for every integer \(n \ge 1\text{,}\) \(c_n=3(2^n-1)\text{.}\)

  3. Prove that \(\sum_{j=0}^m 2^j=2^{m+1}-1 \) for every integer \(m \ge 0\text{.}\)

  4. Prove that for every integer \(n \ge 0\text{,}\) \(n! \ge n\text{.}\)

  5. Prove that for every integer \(n \ge 0\text{,}\) \(4^{n}-1\) is divisible by 3.

  6. Starting with \(n=2\) and increasing \(n\) from there, calculate the first few values for the product

    \begin{equation*} t_n=\prod_{j=2}^n \left( 1-\frac{1}{j} \right)\text{.} \end{equation*}

    Conjecture a closed formula for \(t_n\) based on the values you have calculated, and use induction to prove that your formula is correct.

  7. Prove that for every integer \(n \ge 1\text{,}\)

    \begin{equation*} \sum_{j=1}^{n}j! \le \frac{1}{2}(n+1)! \end{equation*}

  8. Define \(c_0=1\) and for \(n \ge 1\text{,}\) define \(c_n=n c_{n-1}+1\text{.}\) Prove by induction: for \(n \ge 0\text{,}\)

    \begin{equation*} c_n = \sum_{j=0}^n\frac{n!}{(n-j)!}\text{.} \end{equation*}