Lesson 3: Proving sum formulas by induction
Counting cannonballs in a triangular stack
SkillsProving sum formulas by inductionSigma notation
Worked example
Cannonballs are stacked in a pyramid with a triangular base. The top layer has ball, the next layer has , the next has , and in general layer has balls.
(a) Write the number of balls in a stack of layers in sigma notation.
(b) Prove by mathematical induction that a stack of layers has balls, for all .
(c) A museum's stack has balls. How many layers does it have?
Step 1: (a) Add up the layers
Layer has balls, for . So the stack has
Step 2: (b) Initial statement
Let be the statement , . When : LHS and RHS . So is true.
Step 3: (b) Assumption statement
Assume is true for some :
Step 4: (b) Inductive step
The target is .
So is true whenever is true.
Both terms share the factor . The first leaves ; the second is and leaves .
Step 5: (b) Conclusion
Since is true and , by the principle of mathematical induction a stack of layers has balls for all .
Step 6: (c) Solve for the number of layers
Solve , that is, . This is a product of three consecutive integers, and , so try . The stack has layers.
The product grows as grows, so there is only one positive solution. A CAS can solve the cubic directly; by hand, the cube root suggests where to look.
Answer
(a) ; (b) proved for all ; (c) layers.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Write the quantity for one layer, then sum over the layers.
Prove the closed form by induction, taking out the common factor in the inductive step.
Use the closed form to answer the question in context.
Watch out for
Treating the layer sizes as an arithmetic sequence. They are the triangular numbers.
Answering (c) with a decimal: the number of layers must be a positive integer.