Proof by induction: sums of series and divisibility
Proof by mathematical induction lets you prove a statement about every positive integer in a few lines of algebra, even though there are infinitely many cases.
It is the proof method of Core Pure Mathematics, and it comes back in this unit for matrices, in later units for series and derivatives, and in Further Pure 2 for recurrence relations.
Core Pure content is examined on Paper 1 and Paper 2, and either paper may set any of it: an induction proof is a single question of 5 or 6 marks, marked line by line, so the layout you learn here is worth as much as the algebra.
From A level Mathematics
In A level Mathematics you met proof by deduction (start from known facts and reason forwards), proof by exhaustion (check every case), disproof by counter-example and proof by contradiction.
None of them can prove a formula such as for all : checking is still only checking.
Further Mathematics adds induction, which proves the statement for all positive integers at once.
The idea: a chain that never breaks
Think of an infinite row of dominoes.
Two facts are enough to know that every domino falls:
- the first domino falls;
- whenever any one domino falls, it knocks over the next one.
The photograph below shows the start of the chain: the first domino is falling, and every domino stands close enough to the next to knock it over.
Neither fact alone is enough.
Without the push, nothing falls; with gaps in the row, the chain stops at the first gap.
Induction is the same argument for statements.
Write the statement as .
If you show
1. is true (the base case), and
2. if is true for some positive integer , then is true (the inductive step),
then gives , which gives , and so on without end, so is true for every positive integer .
The inductive step is a conditional statement.
You do not know that is true; you assume it, and show that the next case would follow.
The base case is what turns the conditional chain into a real conclusion: without it the dominoes are lined up but nobody pushes the first one.
Why it works (not examined). Suppose the base case and the inductive step are both proved, but the statement fails for some positive integer.
Then there is a smallest positive integer for which it fails.
is not 1, because is true, so is a positive integer for which the statement is true.
The inductive step then makes true, which contradicts the choice of .
So no failing integer exists.
The four parts of every induction proof
Every proof you write has the same four parts, and each earns its own mark.
Part
What you write
Typical mark
Base case
substitute into both sides and show they are equal
B1
Assumption
"Assume the result is true for ", with the formula written out with
M1
Inductive step
the working from to , in place, ending in the target form
M1 (or dM1), A1, A1
Conclusion
"If the result is true for then it is true for . It is true for , so it is true for all positive integers ."
A1
You need to know the kinds of statement induction is used for in this course: sums of series, such as showing that (summed from to ) or that ; divisibility, such as showing that is divisible by 4; and matrix products, such as finding a formula for the power of a matrix.
Sums and divisibility are taught here; matrix powers and the derivatives that recent papers have asked for are in the next section.
Sums of series
For a sum, the step is always the same move: add the th term to the sum of the first terms, which gives the sum of the first terms.
Replace the first part by the assumed formula, then manipulate until you reach the formula with replaced by .
Two habits make this short and safe.
- Write the target first. Before starting the algebra, write down what the formula gives when , and keep it in view. Working towards a stated target is fine, as long as the forward working really reaches it.
- Take out the common factor before expanding. Both the assumed sum and the new term almost always share a factor (often ). Taking it out leaves a quadratic or cubic to tidy, not a quartic to expand and refactorise.
Divisibility
A statement such as " is divisible by 21 for all positive integers " means for some integer .
The step is to write in terms of plus something that is visibly a multiple of the divisor.
Two routes both work:
- Rewrite using index laws (, ), then split off a multiple of .
- Consider (or for a well-chosen ) and show the difference is a multiple of the divisor.
Either way, finish by saying why the result is a multiple: "both terms are multiples of 21, so is divisible by 21".
- Mathematical induction: construct proofs using mathematical induction. Contexts include sums of series, divisibility and powers of matrices.
- Base case: the statement checked for the first value, , by substituting into both sides.
- Inductive step: a proof that if the statement is true for then it is true for .
- Conclusion of an induction proof: true for ; if true for then true for ; so true for all positive integers .
- Divisible by : for some integer .
- Sum of the first positive integers: . You need to know this formula by heart and use it without a reminder. It checks an induction answer quickly (and the unit on series, cp4-6, builds on it), but it never replaces the induction a question asks for.
- Every mark is worth one. M1 is for a correct method applied to this problem; A1 is for an accurate line or answer and needs the M mark before it; B1 is an independent mark (a base case, a value, a reason).
- dM1 depends on the M mark before it, and ddM1 on the two before it. A1* is the last mark of a "show that" or a proof whose result is printed: earned only with no errors and the printed result written out in full, with its subject.
- cso means correct solution only; ft means a wrong earlier value carried forward correctly still earns marks; oe means any equivalent form; awrt means "answers which round to"; isw means ignore subsequent working; a special case (SC) gives partial credit for a recognised wrong route.
- Under the calculator banner ("In this question you must show all stages of your working. Solutions relying entirely on calculator technology are not acceptable.") or a named method ("Prove by induction", "Hence", "By forming and solving a matrix equation"), a correct answer reached another way scores 0 or a special case.
- Radians are the default in complex numbers: a method worked in degrees mode can earn the M mark but never the A mark.
- The last mark of an induction proof needs every earlier mark: the base case, the step reaching the target form and the full conclusion.
- If you make two attempts and cross neither out, the examiner marks the most complete final one: cross out the attempt you do not want.
Prove by induction that, for all positive integers ,
When : left side ; right side .
So the result is true for .
B1 (both sides worked with substituted)
Assume the result is true for , so .
Then
M1 (assumed sum plus the th term)
Target: .
dM1 (the two terms combined, here by taking out the common factor )
A1
, which is the result with .
A1
If the result is true for then it is true for .
It is true for , so it is true for all positive integers .
A1 (needs all previous marks)
Answer: proved.
A candidate who expands to and stops, without showing it equals , scores B1 M1 dM1 A0 A0 A0.
Prove by induction that, for ,
When : left side ; right side .
True for .
B1
Assume true for .
Then
M1
dM1 (one common denominator)
The numerator is .
Putting gives , so is a factor, and .
A1
A1 (the result with )
If true for then true for ; true for ; so true for all .
A1
Answer: proved.
On these papers , so "" means the same as "for all positive integers ".
The factor theorem is the quick way to spot the factorisation the target needs: the target has on top, so must divide the numerator.
Prove by induction that, for all positive integers , is divisible by 21.
(6)
, which is divisible by 21, so the result is true for .
B1
Assume that is divisible by 21, so for some integer .
M1 (assumption stated)
M1 (index laws to bring in the parts of )
A1
, which is divisible by 21.
A1
If is divisible by 21 then is divisible by 21.
is divisible by 21, so is divisible by 21 for all positive integers .
A1
Alternative method: , so , the same line.
Both routes earn full marks; the rewriting route is usually shorter.
Prove by induction that is divisible by 6 for all positive integers .
(6)
Let .
Then , so true for .
B1
Assume for some integer .
M1
M1
A1
is the product of two consecutive integers, so it is even, and is a multiple of 30, so a multiple of 6.
Then is a sum of multiples of 6.
A1 (the reason the difference is a multiple of 6 must be given)
If true for then true for ; true for ; so is divisible by 6 for all positive integers .
A1
Answer: proved.
Writing " is a multiple of 6" with no reason loses the fifth mark: is not obviously a multiple of 6 until you factorise and use the evenness of .
The induction conclusion is a mark of its own and the one lost most often.
It needs all three ideas: "true for ", "if true for then true for " and "true for all positive integers ".
Writing "true for and " or "true for all real numbers" loses it.
A narrative sentence that contains all three ideas is credited.
- A base case with no substitution shown. Writing "true for " or "" alone loses B1. Show put into both sides, because the mark is for checking the formula, not for asserting it.
- Using summation formulae in place of induction. Evaluating with and proves the formula, but a question that says "Prove by induction" gives no marks for it. The command names the method.
- Expanding everything. Expanding the assumed sum and the new term to a quartic and then trying to factorise is long and error-prone. Take out the common factor first, as in Worked example 1; examiners report that spotting it is what separates quick, correct steps from stalled ones.
- Side working. The step must be worked in place, line by line, with at least one line between the assumed form and the target. A jump to the form with the working in the margin is treated as unsupported.
- Assuming what you want to prove. "Assume true for all " is circular. You assume only the case , then prove the next one.
Check your understanding
1. Prove by induction that, for all positive integers ,
Total [6]
2. Prove by induction that, for , is divisible by 64. (6) Total [6]
3. A student ends an induction proof with the sentence "So the result is true for and for , so it is true."
(a) State what is missing from this conclusion. (1)
(b) Write down a conclusion that would earn the final mark. (1)
Total [2]
4. (a) Prove by induction that, for all positive integers ,
\
(b) Hence determine the value of . (2) Total [8]
5. Prove by induction that is divisible by 7 for all positive integers . (5) Total [5]
6. A student is asked to prove by induction that . The student writes and simplifies it correctly to . Explain why this answer scores no marks. (1) Total [1]
Answers
1. : left side ; right side , so true for B1 Assume true for ; M1 dM1 A1 A1 (uses ) If true for then true for ; true for ; so true for all positive integers A1
2. , divisible by 64 B1 Assume ; M1 M1 A1 So , divisible by 64 A1 If true for then true for ; true for ; so true for all A1
3. (a) It never says the result is true for , and it does not say that truth for implies truth for ; it also does not say "for all positive integers " B1
(b) "If the result is true for then it is true for . It is true for , so it is true for all positive integers ." B1
4. (a) : left side ; right side B1
Assume true for ; sum to M1
dM1
A1
A1
Conclusion with all three ideas A1
(b) , where is the formula M1
A1
5. B1 Assume ; M1 A1 , divisible by 7 A1 Conclusion with all three ideas A1
6. The question names the method: a direct use of the summation formulae is not a proof by induction, so it earns no marks however correct it is B1