Skip to main content

Section 4.2 Induction

The basic idea of an induction proof is to proceed step by step. We prove the base case is true, and the induction step retains truth as we move from \(\phi(n)\) to \(\phi(n+1)\text{.}\)

A full written proof by induction has the following four parts:

  1. a clear and explicit statement of the claim and the intent to prove it by induction;

  2. a proof of the Base Case \(\phi(n_0)\text{;}\)

  3. a clear assumption of the induction hypothesis, e.g. “let \(n\geq n_0\text{,}\) and assume that \(\phi(n)\) holds”;

  4. a deduction of \(\phi(n+1)\) from the premise \(\phi(n)\text{.}\)

For any \(n\in\NN\text{,}\) let \(\phi(n)\) be the statement that \(\sum_{k=1}^{n}k=\frac{n(n+1)}{2}\text{.}\) We prove \(\phi(n)\) for all \(n\in\NN\) by induction.

Base Case: First let's prove \(\phi(1)\text{.}\) This is the assertion that

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

Thus, the base case is true.

Induction Step: Let \(n\in \NN\text{.}\) Assume \(\phi(n)\) holds and consider

\begin{equation*} \sum_{k=1}^{n+1}k =\left( \sum_{k=1}^{n} k\right) + (n+1) = \frac{n(n+1)}{2} +(n+1) = \frac{(n+1)(n+2)}{2}\text{.} \end{equation*}

where we used the induction hypothesis \(\phi(n)\) to replace \(\sum_{k=1}^{n} k\) with \(\frac{n(n+1)}{2}\text{.}\) Hence \(\sum_{k=1}^{n+1}k=\frac{(n+1)(n+2)}{2}\) which proves the implication \(\phi(n)\implies \phi(n+1)\text{.}\)

Prove the following formulas for all \(n\in\NN\) by induction:

  1. \(\sum_{k=1}^{n} k^{2} = \frac{n(n+1)(2n+1)}{6}\text{.}\)

  2. \(\sum_{k=1}^{n} k^{3} = \left(\frac{n(n+1)}{2}\right)^{2}\text{.}\)

It turns out that for all powers \(p\) there is a degree \(p+1\) polynomial that gives a formula for the value of \(\sum_{k=1}^{n} k^{p}\text{.}\) To learn more, look up Bernoulli numbers.

Some statements may not be true for all \(n\geq 1\) but maybe for \(n\geq k\) for some \(k\text{,}\) and depending on the problem you will need to figure out what this \(k\) is.

For which \(n\in\NN\) do we have \(2^{n}\lt n!\text{?}\) If we plug in \(n=1,2,3\) this inequality fails, but for \(n\geq 4\) it starts to hold. This gives rise to the following conjecture:

Claim: \(2^{n}\lt n!\) for \(n\geq 4\text{.}\)

Let's prove it by induction. Let \(\phi(n)\) be the statement that \(2^{n}\lt n!\text{.}\)

  • Base case: The base case is \(n=4\text{,}\) and it holds because \(2^{4} = 16 \lt 4!=24\text{.}\)

  • Induction Step: Let \(n\geq 4\text{,}\) and assume \(\phi(n)\text{,}\) i.e. \(2^{n}\lt n!\text{,}\) then

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

Some problems can be proven with or without induction:

Prove that \(n^{3}-n\) is divisible by \(6\) for all \(n\in\mathbb{N}\text{,}\) first by induction, then without induction.

The following formula will be very useful throughout this course:

The second equation follows from the first (just by adding \(1\)), so we just need to prove the first. We prove this by induction.

  • Base case: If \(N=1\text{,}\) then

    \begin{equation*} \frac{x-x^{2}}{1-x} = \frac{x(1-x)}{1-x}=x=\sum_{n=1}^{1} x^{n}\text{.} \end{equation*}

  • Induction Step: Let \(N\in\NN\text{,}\) and suppose (4.2.1) holds for some \(N\text{.}\) Then

    \begin{equation*} \sum_{n=1}^{N+1} x^{n} =x^{N+1}+ \sum_{n=1}^{N} x^{n} =x^{N+1} + \frac{x-x^{N+1}}{1-x} =\frac{x^{N+1}-x^{N+2}}{1-x} + \frac{x-x^{N+1}}{1-x} =\frac{x-x^{N+2}}{1-x}\text{.} \end{equation*}

Mathematical induction is great, but there will be cases in which we need a little more power in the induction step. Sometimes we struggle to deduce \(\phi(n+1)\) from \(\phi(n)\) alone; sometimes it is helpful to be able to assume that \(\phi(k)\) holds for all \(k \leq n\) in order to deduce \(\phi(n+1)\text{.}\) For this reason, we also have Strong Induction.