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 .
- In the inductive step, split off , 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 , 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 fill a rectangle, so the sum is . The same picture with columns suggests .
Proving a sum formula by induction
Define the statement
Let be the statement for .
Initial statement
Evaluate both sides at : the left side is and the right side is . Show they are equal.
Assumption statement
Assume is true for some : .
Write the target
Write : . Simplify so you know exactly what you are aiming for.
Inductive step
Start from the left side: by the assumption. Simplify, factorising towards .
Conclusion
Since is true and , by the principle of mathematical induction is true for all .
Notice the move in the inductive step: the factor in both terms is exactly the factor the target needs.
Worked example
Prove
Prove by mathematical induction that
for all .
Step 1: Initial statement
Let be the statement , . When : LHS and RHS . So is true.
Step 2: Assumption statement
Assume is true for some :
Step 3: Write the target
says
Replace by everywhere: becomes , and becomes .
Step 4: Split off the last term and use the assumption
Step 5: Take out the common factor
Both terms contain , and so does the target. Taking it out now saves expanding to a cubic.
Step 6: Factorise to reach the target
, so
This is the right-hand side of , so is true whenever is true.
The target says the remaining factors must be and . Check: .
Step 7: Conclusion
is true, and true implies true. By the principle of mathematical induction, for all .
Try it yourself first, then check the working one step at a time.
Answer
Proved: the formula holds for , and whenever it holds for it holds for .
Method
Define and check .
Assume and write the target .
Split off and use the assumption on the rest.
Take out the common factor the target shows, then factorise what is left.
Write the conclusion.
Watch out for
Writing the target with instead of .
Expanding 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 contains , and so do both terms of . Take it out first:
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 , you reach . Write this as a single factorised expression.
You are proving . What is the target expression in the inductive step?
The full proof that
Let be the statement , .
Initial statement. When : LHS and RHS , so is true.
Assumption statement. Assume for some .
Inductive step. The target is .
So is true whenever is true.
Conclusion. is true and , so by the principle of mathematical induction is true for all .
Watch the limits. If the upper limit is , then moving from to moves the upper limit from to , so the sum gains two terms. The next example uses the syllabus's own sum.
Worked example
Prove
The syllabus writes . Prove by mathematical induction that
for all .
Step 1: Initial statement
Let be the statement , . When the upper limit is : LHS and RHS . So is true.
Step 2: Assumption statement
Assume is true for some :
Step 3: See what changes
For the upper limit is . So the sum gains two terms, and . The target is .
Increasing by increases the upper limit by , so two new terms appear, not one.
Step 4: Inductive step
This is the right-hand side of , so is true whenever is true.
Twice a power of is the next power: . That happens twice here.
Step 5: Conclusion
Since is true and , by the principle of mathematical induction for all .
Try it yourself first, then check the working one step at a time.
Answer
Proved for all . The inductive step adds two terms, and , because the upper limit rises by .
Method
Work out how the limits change from to .
Split off every new term, not just one.
Use the assumption on the rest, then simplify to the target.
Watch out for
Adding only one new term, or .
Writing . Adding two equal powers doubles them: .
Going from to , which terms are added to ?
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
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.
Try it yourself first, then check the working one step at a time.
Answer
(a) ; (b) proved for all ; (c) layers.
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.
Common mistake
Where sum proofs go wrong
- The wrong new term. replaces the index by everywhere.
- Working on both sides at once. Start from the left side of and work to the right side in one chain. Manipulating both sides of until they match assumes what you are proving.
- Forgetting the assumption. Label the line where you use .
- Algebra slips. Test your expression for the sum to terms at : it must equal .
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 , use the assumption, simplify to the target.
Write the target, , 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 or , each step from to adds more than one term.
Finished the lesson?
Try the 3 quick checks above and the lesson completes itself, or mark it complete now.