7.1: Principle of Mathematical Induction

Axiom \(\PageIndex{1}\)

Suppose \(P(n)\) is a predicate where the variable \(n\) has domain the positive, whole numbers. If

\(P(1)\) is true, and

\((\forall k) (P(k) \rightarrow P(k+1))\) is true,

then \((\forall n)P(n)\) is true.

It is usual to take the principle of mathematical induction as an axiom; that is, we assume that mathematical induction is valid without proving it.

A look ahead.

We will discuss axioms a little more in Chapter 8.

Below is an outline of the idea behind why it is reasonable to assume that mathematical induction is valid. However, this outline does not constitute a proof since it technically uses mathematical induction implicitly.

Idea

Suppose \(n\) is fixed. We have a sequence of valid arguments: 

\(\begin{equation}
\begin{array}
P(1) \rightarrow P(2) & \qquad P(2) \rightarrow P(3) &  \qquad \cdots & \qquad P(n-1) \rightarrow P(n) \\
P(1) & \qquad P(2) & & \qquad P(n-1) \\
 \hline P(2) &  \hline \qquad P(3) &&  \hline \qquad P(n) 
\end{array}
\end{equation}\)

Each is valid (modus ponens). So if we make the two assumptions stated in the principles (i.e. that \(P(1)\) is true and that \(P(k) \rightarrow P(k+1)\) is always true) we can trace the flow of truth from premises to conclusion in each argument in turn: 

Definition: First Argument

Premises true so conclusion is true.

Definition: Second Argument

Premises true (using conclusion of the first argument) so conclusion is true.

Definition: Third Argument

…

Definition: \((n-1)^{th}\) argument

Premises true (using conclusion of the \((n-2)^{th}\) argument) so conclusion is true.

The conclusion of \((n-1)^{th}\) argument is \(P(n)\text{,}\) so \(P(n)\) is true.

Now, here is some specific terminology associated to proofs by induction.

Definition: Base case

the statement \(P(1)\) in a proof by mathematical induction

Definition: Induction Step

the portion of a proof by mathematical induction that establishes the statement \((\forall k) ( P(k) \rightarrow P(k+1) )\)

Definition: Induction Hypothesis

the assumption \(P(k)\) made as the first step in the induction step of a proof by mathematical induction

Procedure \(\PageIndex{1}\): Proof by Induction

To prove a universal statement indexed by whole numbers:

Base case.
Start by proving the statement obtained from the universally quantified predicate for the base case \(n = 1\text{.}\)

Induction step.
Next, assume that \(k\) is a fixed number such that \(k \ge 1\text{,}\) and that the statement obtained from the universally quantified predicate is true for \(n = k\text{.}\) Based on this assumption, try to prove that the next case, \(n=k+1\text{,}\) is also true.

Example \(\PageIndex{1}\)

Prove that the sum of the first \(n\) positive integers is

\begin{equation*} \dfrac{n(n+1)}{2}\text{.} \end{equation*}

Solution

We want to prove \((\forall n)P(n)\text{,}\) where \(P(n)\) is as follows.

\begin{gather*} P(1) \colon \:\: 1 = \dfrac{1\cdot 2}{2}, \qquad P(2) \colon \:\: 1 + 2 = \dfrac{2 \cdot 3}{2}, \qquad P(3) \colon \:\: 1 + 2 + 3 = \dfrac{3 \cdot 4}{2},\\ \dotsc, \qquad P(n) \colon \:\: 1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}, \qquad \dotsc \end{gather*}

We will prove this by induction.

Base case.
\(1 = (1\cdot2)/2\) is obviously true.

Induction step.
Assume the statement is true for \(n=k\text{;}\) i.e. assume that

\begin{equation*} 1 + 2 + \cdots + k = k(k+1)/2 \text{.} \end{equation*}
We want to show that this implies the statement is true for \(n = k+1\text{;}\) i.e. show

\begin{equation*} 1 + 2 + \cdots + k + (k+1) = (k+1)(k+2)/2\text{.} \end{equation*}
We have

\begin{align*} 1 + 2 + \cdots + k + (k+1) & = (1 + 2 + \cdots + k) + (k+1) \\ & = \dfrac{k(k+1)}{2} + (k+1) \\ & = \dfrac{k^2 + 3k + 2}{2} \\ & = \dfrac{(k+1)(k+2)}{2} \text{.} \end{align*}

Example \(\PageIndex{2}\)

Prove that \(n^3 + (n+1)^3 + (n+2)^3\) is always divisible by \(9\) for every \(n \ge 1\text{.}\)

Solution

We want to prove \((\forall n)P(n)\text{,}\) where \(P(n)\) is as follows.

\begin{align*} P(1) & \colon \quad 1^3 + 2^3 + 3^3 \text{ is divisible by } 9 \\ P(2) & \colon \quad 2^3 + 3^3 + 4^3 \text{ is divisible by } 9 \\ P(3) & \colon \quad 3^3 + 4^3 + 5^3 \text{ is divisible by } 9 \\ & \vdots \\ P(n) & \colon \quad n^3 + (n+1)^3 + (n+2)^3 \text{ is divisible by } 9 \\ & \vdots \end{align*}
We will prove this by induction.

Base case.
For \(n=1\text{,}\) \(n^3 + (n+1)^3 + (n+2)^3 = 36 = 9\cdot 4\text{.}\)

Induction step.
Assume \(k^3 + (k+1)^3 + (k+2)^3\) is divisible by \(9\text{.}\) This means that there exists some whole number \(m\) so that

\begin{equation*} k^3 + (k+1)^3 + (k+2)^3 = 9 m \text{.} \end{equation*}
We want to show that \((k+1)^3 + (k+2)^3 + (k+3)^3\) is also divisible by \(9\text{.}\) To make the connection between this sum of cubes and the “previous case” sum of cubes above, we can add in (and simultaneously subtract out) a \(k^3\) term:

\begin{align*} (k+1)^3 + (k+2)^3 + (k+3)^3 & = (k^3 + (k+1)^3 + (k+2)^3) + (k+3)^3 - k^3 \\ & = 9m + (k+3)^3 - k^3 \\ & = 9m + (k^3 + 9k^2 + 27k + 27) - k^3 \\ & = 9(m + k^2 + 3k + 3) \text{.} \end{align*}
Since we have factored our sum of cubes into a product involving \(9\text{,}\) that sum of cubes is divisible by \(9\text{.}\)

 

 

Example \(\PageIndex{1}\)

Prove that \(3^{3n} + 1\) is divisible by \(7\) whenever \(n\) is odd.

Solution

We do not want to use \(n\) as our induction index, since it jumps by twos. But \(n\) odd means that \(n = 2m - 1\) for some \(m\ge 1\text{,}\) so we want to prove \((\forall m)P(m)\text{,}\) where \(P(m)\) is as follows.

\begin{align*} P(1) & \colon \quad 3^3 + 1 \text{ is divisible by } 7 \\ P(2) & \colon \quad 3^9 + 1 \text{ is divisible by } 7 \\ P(3) & \colon \quad 3^{15} + 1 \text{ is divisible by } 7 \\ & \vdots \\ P(m) & \colon \quad 3^{6m-3} + 1 \text{ is divisible by } 7 \\ & \vdots \end{align*}
We will prove this by induction. 

Base case.
For \(m=1\text{,}\) \(3^3+1 = 28 = 7\cdot 4\text{.}\)

Induction step.
Assume \(3^{6k-3} + 1\) is divisible by \(7\text{.}\) This means that there exists some whole number \(\ell\) so that

\begin{equation*} 3^{6k-3} + 1 = 7 \ell \text{.} \end{equation*}
We want to show \(3^{6(k+1)-3} + 1\) is divisible by \(7\text{.}\) We have

\begin{align*} 3^{6 (k + 1) - 3} + 1 & = (3^{6k - 3}) (3^6) + 1 \\ & = (3^{6k-3} + 1 - 1) (3^6) + 1 \\ & = (3^{6k-3} + 1) (3^6) - 3^6 + 1 \\ & = (7 \ell) (3^6) - 728 \\ & = 7 (3^6 \ell - 104) \text{.} \end{align*}
Since we have our expression factored into a product involving \(7\text{,}\) our expression is divisible by \(7\) as desired.

 

Remark \(\PageIndex{1}\)

Indexing of statements does not have to start at \(1\text{.}\)

Example \(\PageIndex{1}\)

Prove \(2^n \lt n!\) whenever \(n \ge 4\text{.}\)

Note

This statement is actually false for \(n=1,2,3\text{.}\)
 

Solution

Base case.
For \(n=4\text{,}\) \(2^4 = 16\) and \(4! = 24\text{.}\)

Induction step.
Assume \(2^k \lt k!\) for some \(k \ge 4\text{.}\) We want to show \(2^{k+1} \lt (k+1)!\text{.}\) We have

\begin{equation*} 2^{k+1} = 2(2^k) \lt 2(k!) \lt (k+1)(k!) = (k+1)! \text{.} \end{equation*}