Lesson 3: Proving sum formulas by induction

Counting cannonballs in a triangular stack

SkillsProving sum formulas by inductionSigma notation

Worked example

  • 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?

1 of 6 steps
  1. Step 1: (a) Add up the layers

    Layer rr has r(r+1)2\frac{r(r+1)}{2} balls, for r=1,2,…,nr = 1, 2, \ldots, n. So the stack has

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

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

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.

Save your progress with a free account