Skip to main content

Section 6.2 The Extended Principle of Mathematical Induction

A little exploration shows that the following proposition appears to be true.

Proposition.

For each integer \(n\) with \(n \geq 4\text{,}\) \(n! > n^4\text{.}\)

We would like to use mathematical induction to prove this, but the proposition has the added assumption that \(n \geq 4\text{.}\) So to do this, we use a slight modification of the Principle of Mathematical Induction called the Extended Principle of Mathematical Induction.

The Extended Principle of Mathematical Induction.

Let \(M\) be an integer. If \(T\) is a subset of \(\Z\) such that

  • \(M \in T\text{,}\) and

  • For every \(k \in \Z\) with \(k \geq M\text{,}\) if \(k \in T\text{,}\) then \((k + 1) \in T\text{,}\)

then \(T\) contains all integers greater than or equal to \(M\text{.}\) That is, \(\{ n \in \Z | n \geq M \} \subseteq T\text{.}\)

The primary use of the Principle of Mathematical Induction is to prove statements of the form

\begin{equation*} ( \forall n \in \Z, \text{ with } n \geq M)(P(n))\text{,} \end{equation*}

where \(M\) is an integer and \(P (n)\) is some open sentence. (In most induction proofs, we will use a value of \(M\) that is greater than or equal to zero.) So our goal is to prove that the truth set \(T\) of the predicate \(P (n)\) contains all integers greater than or equal to \(M\text{.}\) So to verify the hypothesis of the Extended Principle of Mathematical Induction, we must

  1. Prove that \(M \in T\text{.}\) That is, prove that \(P (M)\) is true.

  2. Prove that for every \(k \in Z\) with \(k \geq M\text{,}\) if \(k \in T\text{,}\) then \((k + 1) \in T\text{.}\) That is, prove that if \(P (k)\) is true, then \(P (k + 1)\) is true.

As before, the first step is called the basis step or the initial step, and the second step is called the inductive step. This means that a proof using the Extended Principle of Mathematical Induction will have the following form:

Using the Extended Principle of Mathematical Induction.

Let \(M\) be an integer. To prove: \(( \forall n \in \Z, \text{ with } n \geq M)(P(n))\)

Basis step

Prove \(P(M)\text{.}\)

Inductive step

Prove that for every \(k \in Z\) with \(k \geq M\text{,}\) if \(P(k)\) is true, then \(P(k + 1)\) is true.

We can then conclude that \(P (n)\) is true for all \(n \in Z\) with \(n \geq M\text{.}\)

This is basically the same procedure as the one for using the Principle of Mathematical Induction. The only difference is that the basis step uses an integer \(M\) other than 1. For this reason, when we write a proof that uses the Extended Principle of Mathematical Induction, we often simply say we are going to use a proof by mathematical induction. We will prove PropositionĀ 6.2 using the Extended Principle of Mathematical Induction.

Proof.

We will use a proof by mathematical induction. For this proof, we let

\(P(n)\) be ā€œ\(n! \gt 2^n\text{.}\)ā€
We first prove that \(P (4)\) is true. Using \(n = 4\text{,}\) we see that \(4! = 24\) and \(2^4 = 16\text{.}\) This means that \(4! \gt 2^4\) and, hence, \(P (4)\) is true.

For the inductive step, we prove that for all \(k \in N\) with \(k \geq 4\text{,}\) if \(P (k)\) is true, then \(P (k + 1)\) is true. So let \(k\) be a natural number greater than or equal to 4, and assume that \(P (k)\) is true. That is, assume that

\begin{equation} k! \gt 2^k\text{.}\tag{8} \end{equation}

The goal is to prove that \(P (k + 1)/\) is true or that \((k + 1)! > 2^{k+1}\) . Multiplying both sides of inequality (8) by \(k + 1\) gives

\begin{align} (k + 1)! \amp \gt (k + 1) \cdot 2^k \text{, or}\notag\\ (k + 1)! \amp \gt (k + 1) \cdot 2^k\text{.}\tag{9} \end{align}

Now, \(k \geq 4\text{.}\) Thus, \(k + 1 \gt 2\text{,}\) and hence \((k + 1) \cdot 2^k \gt 2 \cdot 2^k\text{.}\) This means that

\begin{equation} (k + 1) \cdot 2^k \gt 2^{k+1}\tag{10} \end{equation}

Inequalities (9) and (10) show that

\begin{equation*} (k + 1)! \gt 2^{k+ 1}\text{,} \end{equation*}

and this proves that if \(P (k)\) is true, then \(P (k + 1)\) is true. Thus, the inductive step has been established, and so by mathematical induction, we have proved that \(n! \gt 2^n\) for each natural number \(n\) with \(n \geq 4\text{.}\)