Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Section 7.1 Principle of Mathematical Induction

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:
\(P(1) \lgccond P(2)\)
\(P(1)\)
\(P(2)\)
\(P(2) \lgccond P(3)\)
\(P(2)\)
\(P(3)\)
\begin{equation*} \cdots \end{equation*}
\(P(n-1) \lgccond P(n)\)
\(P(n-1)\)
\(P(n)\)
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) \lgccond P(k+1)\) is always true) we can trace the flow of truth from premises to conclusion in each argument in turn:
First argument
Premises true so conclusion is true.
Second argument
Premises true (using conclusion of the first argument) so conclusion is true.
Third argument
…
\(\nth[(n-1)]\) argument
Premises true (using conclusion of the \(\nth[(n-2)]\) argument) so conclusion is true.
The conclusion of \(\nth[(n-1)]\) argument is \(P(n)\text{,}\) so \(P(n)\) is true.
Now, here is some specific terminology associated to proofs by induction.
base case
the statement \(P(1)\) in a proof by mathematical induction
induction step
the portion of a proof by mathematical induction that establishes the statement \((\forall k) \bbrac{ P(k) \lgccond P(k+1) }\)
induction hypothesis
the assumption \(P(k)\) made as the first step in the induction step of a proof by mathematical induction

Worked Example 7.1.3.

Prove that the sum of the first \(n\) positive integers is
\begin{equation*} \frac{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 = \frac{1\cdot 2}{2}, \qquad P(2) \colon \:\: 1 + 2 = \frac{2 \cdot 3}{2}, \qquad P(3) \colon \:\: 1 + 2 + 3 = \frac{3 \cdot 4}{2},\\ \dotsc, \qquad P(n) \colon \:\: 1 + 2 + \dotsb + n = \frac{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 + \dotsb + 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 + \dotsb + k + (k+1) = (k+1)(k+2)/2\text{.} \end{equation*}
We have
\begin{align*} 1 + 2 + \dotsb + k + (k+1) \amp = (1 + 2 + \dotsb + k) + (k+1) \\ \amp = \frac{k(k+1)}{2} + (k+1) \\ \amp = \frac{k^2 + 3k + 2}{2} \\ \amp = \frac{(k+1)(k+2)}{2} \text{.} \end{align*}

Worked Example 7.1.4.

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) \amp \colon \quad 1^3 + 2^3 + 3^3 \text{ is divisible by } 9 \\ P(2) \amp \colon \quad 2^3 + 3^3 + 4^3 \text{ is divisible by } 9 \\ P(3) \amp \colon \quad 3^3 + 4^3 + 5^3 \text{ is divisible by } 9 \\ \amp \vdots \\ P(n) \amp \colon \quad n^3 + (n+1)^3 + (n+2)^3 \text{ is divisible by } 9 \\ \amp \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 \amp = \bbrac{k^3 + (k+1)^3 + (k+2)^3} + (k+3)^3 - k^3 \\ \amp = 9m + (k+3)^3 - k^3 \\ \amp = 9m + (k^3 + 9k^2 + 27k + 27) - k^3 \\ \amp = 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{.}\)

Worked Example 7.1.5.

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) \amp \colon \quad 3^3 + 1 \text{ is divisible by } 7 \\ P(2) \amp \colon \quad 3^9 + 1 \text{ is divisible by } 7 \\ P(3) \amp \colon \quad 3^{15} + 1 \text{ is divisible by } 7 \\ \amp \vdots \\ P(m) \amp \colon \quad 3^{6m-3} + 1 \text{ is divisible by } 7 \\ \amp \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 \amp = (3^{6k - 3}) (3^6) + 1 \\ \amp = (3^{6k-3} + 1 - 1) (3^6) + 1 \\ \amp = (3^{6k-3} + 1) (3^6) - 3^6 + 1 \\ \amp = (7 \ell) (3^6) - 728 \\ \amp = 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 7.1.6.

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

Worked Example 7.1.7.

Prove \(2^n \lt n!\) whenever \(n \ge 4\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*}
<Prev^TopNext>