Lesson 3 of 7 · 20 min

Proving sum formulas by induction

Prove a formula for a sum for every positive integer n by splitting off the last term, using the assumption on the rest and factorising towards the target.

What you will be able to do

  • Write a complete proof by induction of a formula for ∑r=1nTr\sum_{r=1}^{n} T_r.
  • In the inductive step, split off Tk+1T_{k+1}, use the assumption and factorise towards the target.
  • Adapt the method when the limits make each step add more than one term.

Gauss's trick gave ∑r=1nr=n(n+1)2\sum_{r=1}^{n} r = \frac{n(n+1)}{2}, and the picture below shows the same idea. But a clever trick for one sum doesn't help with the next one. Induction does: once you have a formula, whether from a pattern, a picture or a guess, induction can prove it for every positive integer.

Two copies of 1+2+3+4+51 + 2 + 3 + 4 + 5 fill a 5×65 \times 6 rectangle, so the sum is 5×62=15\frac{5 \times 6}{2} = 15. The same picture with nn columns suggests n(n+1)2\frac{n(n+1)}{2}.

Proving a sum formula by induction

  1. Define the statement

    Let P(n)P(n) be the statement ∑r=1nTr=f(n)\sum_{r=1}^{n} T_r = f(n) for n∈Z+n \in \mathbb{Z}^+.

  2. Initial statement

    Evaluate both sides at n=1n = 1: the left side is T1T_1 and the right side is f(1)f(1). Show they are equal.

  3. Assumption statement

    Assume P(k)P(k) is true for some k∈Z+k \in \mathbb{Z}^+: ∑r=1kTr=f(k)\sum_{r=1}^{k} T_r = f(k).

  4. Write the target

    Write P(k+1)P(k+1): ∑r=1k+1Tr=f(k+1)\sum_{r=1}^{k+1} T_r = f(k + 1). Simplify f(k+1)f(k + 1) so you know exactly what you are aiming for.

  5. Inductive step

    Start from the left side: ∑r=1k+1Tr=∑r=1kTr+Tk+1=f(k)+Tk+1\sum_{r=1}^{k+1} T_r = \sum_{r=1}^{k} T_r + T_{k+1} = f(k) + T_{k+1} by the assumption. Simplify, factorising towards f(k+1)f(k + 1).

  6. Conclusion

    Since P(1)P(1) is true and P(k)⇒P(k+1)P(k) \Rightarrow P(k+1), by the principle of mathematical induction P(n)P(n) is true for all n∈Z+n \in \mathbb{Z}^+.

Interactive

Prove ∑r=1nr=n(n+1)2\sum_{r=1}^{n} r = \frac{n(n+1)}{2}

Notice the move in the inductive step: the factor (k+1)(k + 1) in both terms is exactly the factor the target needs.

Worked example

Prove ∑r=1nr2=n(n+1)(2n+1)6\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}

  • Complex familiar
  • Technology free

Prove by mathematical induction that

∑r=1nr2=n(n+1)(2n+1)6\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}

for all n∈Z+n \in \mathbb{Z}^+.

7 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Define P(n)P(n) and check n=1n = 1.

  2. Assume P(k)P(k) and write the target P(k+1)P(k+1).

  3. Split off Tk+1T_{k+1} and use the assumption on the rest.

  4. Take out the common factor the target shows, then factorise what is left.

  5. Write the conclusion.

Watch out for

  • Writing the target with 2k+12k + 1 instead of 2k+32k + 3.

  • Expanding k(k+1)(2k+1)k(k+1)(2k+1) completely and then struggling to factorise a cubic.

Tip

Factorise, don't expand

The target tells you which factors to look for. In the sum of squares the target (k+1)(k+2)(2k+3)6\frac{(k+1)(k+2)(2k+3)}{6} contains (k+1)(k + 1), and so do both terms of k(k+1)(2k+1)6+(k+1)2\frac{k(k+1)(2k+1)}{6} + (k + 1)^2. Take it out first:

(k+1)[k(2k+1)+6(k+1)]6=(k+1)(2k2+7k+6)6.\frac{(k+1)\big[k(2k+1) + 6(k+1)\big]}{6} = \frac{(k+1)\left(2k^2 + 7k + 6\right)}{6}.

Now only a quadratic is left to factorise. Expanding everything into a cubic first is slower and easier to get wrong.

In the inductive step for ∑r=1nr(r+1)=n(n+1)(n+2)3\sum_{r=1}^{n} r(r + 1) = \frac{n(n+1)(n+2)}{3}, you reach k(k+1)(k+2)3+(k+1)(k+2)\frac{k(k+1)(k+2)}{3} + (k + 1)(k + 2). Write this as a single factorised expression.

Reads asYour answer shows here as maths.

You are proving ∑r=1n1r(r+1)=nn+1\sum_{r=1}^{n} \frac{1}{r(r+1)} = \frac{n}{n+1}. What is the target expression in the inductive step?

Choose one answer
The full proof that ∑r=1n1r(r+1)=nn+1\sum_{r=1}^{n} \frac{1}{r(r+1)} = \frac{n}{n+1}

Let P(n)P(n) be the statement ∑r=1n1r(r+1)=nn+1\sum_{r=1}^{n} \frac{1}{r(r+1)} = \frac{n}{n+1}, n∈Z+n \in \mathbb{Z}^+.

Initial statement. When n=1n = 1: LHS =11×2=12= \frac{1}{1 \times 2} = \frac{1}{2} and RHS =12= \frac{1}{2}, so P(1)P(1) is true.

Assumption statement. Assume ∑r=1k1r(r+1)=kk+1\sum_{r=1}^{k} \frac{1}{r(r+1)} = \frac{k}{k+1} for some k∈Z+k \in \mathbb{Z}^+.

Inductive step. The target is k+1k+2\frac{k+1}{k+2}.

∑r=1k+11r(r+1)=kk+1+1(k+1)(k+2)using the assumption=k(k+2)+1(k+1)(k+2)=k2+2k+1(k+1)(k+2)=(k+1)2(k+1)(k+2)=k+1k+2\begin{aligned} \sum_{r=1}^{k+1} \frac{1}{r(r+1)} &= \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} \quad \text{using the assumption} \\ &= \frac{k(k+2) + 1}{(k+1)(k+2)} = \frac{k^2 + 2k + 1}{(k+1)(k+2)} \\ &= \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2} \end{aligned}

So P(k+1)P(k+1) is true whenever P(k)P(k) is true.

Conclusion. P(1)P(1) is true and P(k)⇒P(k+1)P(k) \Rightarrow P(k+1), so by the principle of mathematical induction P(n)P(n) is true for all n∈Z+n \in \mathbb{Z}^+.

Watch the limits. If the upper limit is 2n+12n + 1, then moving from n=kn = k to n=k+1n = k + 1 moves the upper limit from 2k+12k + 1 to 2k+32k + 3, so the sum gains two terms. The next example uses the syllabus's own sum.

Worked example

Prove ∑j=02n+12j=22n+2−1\sum_{j=0}^{2n+1} 2^j = 2^{2n+2} - 1

  • Complex unfamiliar
  • Technology free

The syllabus writes ∑j=02n+12j=20+21+22+⋯+22n+1\sum_{j=0}^{2n+1} 2^j = 2^0 + 2^1 + 2^2 + \cdots + 2^{2n+1}. Prove by mathematical induction that

∑j=02n+12j=22n+2−1\sum_{j=0}^{2n+1} 2^j = 2^{2n+2} - 1

for all n∈Z+n \in \mathbb{Z}^+.

5 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Work out how the limits change from n=kn = k to n=k+1n = k + 1.

  2. Split off every new term, not just one.

  3. Use the assumption on the rest, then simplify to the target.

Watch out for

  • Adding only one new term, 22k+22^{2k+2} or 22k+32^{2k+3}.

  • Writing 22k+2+22k+2=24k+42^{2k+2} + 2^{2k+2} = 2^{4k+4}. Adding two equal powers doubles them: 22k+32^{2k+3}.

Going from n=kn = k to n=k+1n = k + 1, which terms are added to ∑j=02n+12j\sum_{j=0}^{2n+1} 2^j?

Choose one answer

Sum formulas also answer questions about real arrangements. Cannonballs, oranges and cans are often stacked in layers that grow by a pattern, and the total is a sum.

Worked example

Counting cannonballs in a triangular stack

  • Complex unfamiliar

Cannonballs are stacked in a pyramid with a triangular base. The top layer has 11 ball, the next layer has 1+2=31 + 2 = 3, the next has 1+2+3=61 + 2 + 3 = 6, and in general layer rr has r(r+1)2\frac{r(r+1)}{2} balls.

(a) Write the number of balls in a stack of nn layers in sigma notation.

(b) Prove by mathematical induction that a stack of nn layers has n(n+1)(n+2)6\frac{n(n+1)(n+2)}{6} balls, for all n∈Z+n \in \mathbb{Z}^+.

(c) A museum's stack has 220220 balls. How many layers does it have?

6 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Write the quantity for one layer, then sum over the layers.

  2. Prove the closed form by induction, taking out the common factor in the inductive step.

  3. Use the closed form to answer the question in context.

Watch out for

  • Treating the layer sizes 1,3,6,10,…1, 3, 6, 10, \ldots as an arithmetic sequence. They are the triangular numbers.

  • Answering (c) with a decimal: the number of layers must be a positive integer.

Common mistake

Where sum proofs go wrong

  • The wrong new term. Tk+1T_{k+1} replaces the index by k+1k + 1 everywhere.
  • Working on both sides at once. Start from the left side of P(k+1)P(k+1) and work to the right side in one chain. Manipulating both sides of P(k+1)P(k+1) until they match assumes what you are proving.
  • Forgetting the assumption. Label the line where you use P(k)P(k).
  • Algebra slips. Test your expression for the sum to k+1k + 1 terms at k=1k = 1: it must equal T1+T2T_1 + T_2.

Exam tip

Where the marks are

Marking guides for a 4 or 5 mark induction proof typically reward the initial statement, the assumption, using the assumption in the inductive step, valid algebra that reaches the target, and the conclusion. Write LHS and RHS, keep every equals sign true, and say "using the assumption" where you use it.

Summary

  • For a sum formula, the inductive step is: split off Tk+1T_{k+1}, use the assumption, simplify to the target.

  • Write the target, f(k+1)f(k + 1), before starting the algebra.

  • Take out the common factors the target shows instead of expanding everything.

  • For sums of fractions, combine over a common denominator, then factorise the numerator.

  • If a limit is 2n2n or 2n+12n + 1, each step from kk to k+1k + 1 adds more than one term.

Finished the lesson?

Try the 3 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 3 of 70% read

Save your progress with a free account