Skip to main content

Section 6.1 Using the Principle of Mathematical Induction

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

\begin{equation*} ( \forall n \in \N)(P(n)) \end{equation*}

where \(P(n)\) is some open sentence. Recall that a universally quantified statement like the preceding one is true if and only if the truth set \(T\) of the open sentence \(P(n)\) is the set \(N\text{.}\) So our goal is to prove that \(T = \N\text{,}\) which is the conclusion of the Principle of Mathematical Induction. To verify the hypothesis of the Principle of Mathematical Induction, we must

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

  2. Prove that 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.

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 by mathematical induction will have the following form:

Procedure for a Proof by Mathematical Induction.

To prove: \(( \forall n \in \N)(P(n))\)

Basis step:

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

Inductive step:

Prove that for each \(k \in N\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 N\text{.}\)

Note that in the inductive step, we want to prove that the conditional statement ā€œfor each \(k \in N\text{,}\) if \(P (k)\) then \(P (k + 1)\)ā€ is true. So we will start the inductive step by assuming that \(P (k)\) is true. This assumption is called the inductive assumption or the inductive hypothesis.

The key to constructing a proof of the inductive step is to discover how \(P (k + 1)/\) is related to \(P (k)\) for an arbitrary natural number \(k\text{.}\) This is why it is important to write down explicitly what \(P (k)\) and \(P (k + 1)\) are within the proof. Notice how this is done in the proof of the following proposition.

Proof.

We will use a proof by mathematical induction. For each natural number \(n\text{,}\) we let \(P (n)\) be

\begin{equation*} 1^2 + 2^2 + \cdots + n^2 = \frac{n (n + 1)(2n + 1)}{6}\text{.} \end{equation*}

We first prove that \(P (1)\) is true. Notice that \(\frac{1(1 + 1)(2 \cdot 1 + 1)}{6} = 1\text{.}\) This shows that

\begin{equation*} 1^2 = \frac{1(1 + 1)(2 \cdot 1 + 1)}{6} \end{equation*}

which proves that \(P(1)\) is true.

For the inductive step, we prove that for each \(k \in N\text{,}\) if \(P (k)\) is true, then \(P (k + 1)\) is true. So let \(k\) be a natural number and assume that \(P (k)\) is true. That is, assume that

\begin{equation} 1^2 + 2^2 + \cdots + k^2 = \frac{k (k + 1)(2k + 1)}{6}\tag{6} \end{equation}

The goal now is to prove that \(P (k + 1)\) is true. That is, is must be proved that

\begin{align} 1^2 + 2^2 + \cdots + k^2 + (k + 1)^2 \amp = \frac{(k + 1)[(k + 1) +1][(2(k + 1) + 1]}{6}\notag\\ \amp = \frac{(k + 1)(k + 2)(2k + 3)}{6}\tag{7} \end{align}

To do this, we add \((k + 1)^2\) to both sides of equation (6) and algebraically rewrite the right side of the resulting equation. This gives

\begin{align*} 1^2 + 2^2 + \cdots + k^2 + (k + 1)^2 \amp = \frac{k (k + 1)(2k + 1)}{6} + (k + 1)^2\\ \amp = \frac{k (k + 1)(2k + 1) + 6(k + 1)^2}{6}\\ \amp = \frac{(k + 1)[k(2k + 1) + 6(k + 1)]}{6}\\ \amp = \frac{(k + 1)(2k^2 + 7k + 6)}{6}\\ \amp = \frac{(k + 1)(k+ 2)(2k + 3)}{6}\text{.} \end{align*}

Comparing this result to equation (7), we see that if \(P (k)\) is true, then \(P (k + 1)\) is true. Hence, the inductive step has been established, and by the Principle of Mathematical Induction, we have proved that for each natural number \(n\text{,}\)

\begin{equation*} 1^2 + 2^2 + \cdots + n^2 = \frac{n (n + 1)(2n + 1)}{6} \end{equation*}