Skip to main content

Section 7.2 Induction with sums

Recall the recursive property of summation:

\begin{equation*} \sum_{i=0}^{k+1} a_i = \Big(\sum_{i=0}^k a_i\Big) + a_{k+1} \end{equation*}

In other words, we can calculate the value of a sum for a given index knowing the value of the sum for a smaller index. Since proof by induction is recursive, this means we can prove values of sums by induction.

As with the other proof-writing chapter, make sure you write down all the proofs!

Let's think about the proof and put the pieces together before we actually write the formal proof.

As we know, proof by induction proceeds in two steps. First we check that the statement is true in the base case. For this theorem, \(n_0=0\text{,}\) so we are trying to prove \(P(0)\text{,}\) which is the statement that

\begin{equation*} \sum_{i=0}^0 i = \dfrac{0(0+1)}{2} \end{equation*}

On the left side we have the sum of a single value, which is \(0\text{.}\) On the right side, \(0\) times anything is \(0\text{.}\) So, the base case is true.

Next, we want to do the inductive step. Assume that \(k\) is some integer that is at least as big as \(0\text{.}\) Then we want to show that if \(P(k)\) is true, meaning that

\begin{equation*} \sum_{i=0}^k i = \dfrac{k(k+1)}{2} \end{equation*}

then \(P(k+1)\text{,}\) meaning

\begin{equation*} \sum_{i=0}^{k+1} i = \dfrac{(k+1)(k+1+1)}{2} \end{equation*}

is true. (Of course, \(k+1+1=k+2\text{,}\) but we are emphasizing the substitution of \(k+1\) for each \(k\text{.}\))

You might want to assume that \(P(k+1)\) is true and “cancel” things to show that \(P(k)\) is true. This is ABSOLUTELY WRONG. As you know, \(P(k)\to P(k+1)\) is not the same sentence as \(P(k+1)\to P(k)\text{.}\) So, make sure you start by assuming that \(P(k)\) is true, and somehow convince your reader that \(P(k+1)\) must also be true.

The path you take will depend on the context of the proof. With sums, the recursive property is fruitful. Keep in mind that we will assume

\begin{equation*} \sum_{i=0}^k i = \dfrac{k(k+1)}{2} \end{equation*}

Under the assumption of the inductive hypothesis, then:

\begin{align*} \sum_{i=0}^{k+1} i \amp = \Big(\sum_{i=0}^k i\Big) + (k+1)\\ \amp = \dfrac{k(k+1)}{2} + (k+1) \end{align*}

Now it is time to do some arithmetic. To add fractions, we must get a common denominator.

\begin{align*} \sum_{i=0}^{k+1} i \amp = \dfrac{k(k+1)}{2} + (k+1)\\ \amp = \dfrac{k(k+1)}{2} + \dfrac{2(k+1)}{2} \end{align*}

You may choose to expand both numerators, add, and simplify. This will certainly end in the conclusion that the numerator is \((k+1)(k+2)\text{,}\) which is desired. However, there is an easier path by factoring:

\begin{align*} \sum_{i=0}^{k+1} i \amp = \dfrac{k(k+1)}{2} + \dfrac{2(k+1)}{2}\\ \amp = \dfrac{k(k+1)+2(k+1)}{2}\\ \amp = \dfrac{(k+1)(k+2)}{2} \end{align*}

We can factor the common \((k+1)\) out of both terms, leaving us with \(k+2\text{.}\) Typically students do not easily think to factor expressions, but if you can train yourself to do so you can skip some nasty arithmetic.

Finally, let's tie the pieces together into the proof.

First, check the base case. Since

\begin{equation*} \sum_{i=0}^0 i = 0 = \frac{0(0+1)}{2}, \end{equation*}

the statement is true in the base case.

Next, suppose that for some integer \(k \ge 0\) that

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

We claim that

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

Expand the sum on the left using our inductive hypothesis:

\begin{align*} \sum_{i=0}^{k+1} i \amp = \Big( \sum_{i=0}^k i \Big) + (k+1)\\ \amp = \dfrac{k(k+1)}{2} + (k+1)\\ \amp = \dfrac{k(k+1)}{2} + \dfrac{2(k+1)}{2}\\ \amp = \dfrac{k(k+1)+2(k+1)}{2}\\ \amp = \dfrac{(k+1)(k+2)}{2} \end{align*}

as claimed.

Therefore by induction,

\begin{equation*} \sum_{0=1}^n i = \frac{n(n+1)}{2} \end{equation*}

for all \(n \ge 1\text{.}\)

In the above proof, we see four steps that will appear in all proofs by induction:

  1. Checking that the statement is true in the base case by substituting \(n=n_0\) into \(P(n)\) and checking to see if the resulting statement is true. This is typically the easiest step of the proof.

  2. Assuming that \(P(k)\) is true for some integer \(k \ge n_0\text{.}\)

  3. Claiming that \(P(k+1)\) is true. Beware that this is not the same as assuming that \(P(k+1)\) is true, which would be logically invalid. By claiming \(P(k+1)\) ahead of time, we alert our reader to the conclusion of the proof, and allow them to get an idea of where we are headed. Plus, it helps us (the proof writer) know what we are looking for, which can make the next step easier.

  4. Proving that \(P(k+1)\) is true by only assuming \(P(k)\text{.}\) The exact work here will depend on the context of the proof.

Let's see another example.

Prove that

\begin{equation*} \sum_{j=1}^n (3j^2-3j+1) = n^3 \end{equation*}

for all \(n \ge 1\text{.}\)

Try to write the proof yourself first. At the very least, set up the “skeleton” of the proof even if you can't quite get the arithmetic right. Then, see the proof below and complete your proof.

As a hint, \((k+1)^3=k^3+3k^2+3k+1\text{.}\)

The statement is true in the base case where \(n=1\) because

\begin{equation*} \sum_{j=1}^1 (3j^2-3j+1) = 1 = 1^3 \end{equation*}

Next, assume there exists an integer \(k \ge 1\) where

\begin{equation*} \sum_{j=1}^k (3j^2-3j+1) = k^3 \end{equation*}

We aim to prove that

\begin{equation*} \sum_{j=1}^{k+1} (3j^2-3j+1) = (k+1)^3 \end{equation*}

Start by expanding the sum on the left according to our inductive hypothesis.

\begin{align*} \sum_{j=1}^{k+1} (3j^2-3j+1) \amp = \sum_{j=1}^k (3j^2-3j+1) + [3(k+1)^2 - 3(k+1) + 1]\\ \amp = k^3 + 3(k+1)^2 - 3(k+1) + 1\\ \amp = k^3 + 3k^2 + 6k + 3 - 3k - 3 + 1\\ \amp = k^3 + 3k^2 + 3k + 1\\ \amp = (k+1)^3 \end{align*}

as desired. Thus, by induction,

\begin{equation*} \sum_{j=1}^n (3j^2-3j+1) = n^3 \end{equation*}

for all integers \(n \ge 1\text{.}\)

In this example, our “factoring trick” doesn't work so we have to get our hands dirty expanding and simplifying the expression.