7.1: Principle of Mathematical Induction

Last updated
Save as PDF

Page ID: 83432

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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.

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*}