Proof by mathematical induction
Studying this course? Keep your progress in one place.
Key facts
- Induction has four parts: basis ( true), assumption ( true), inductive step ( true using ) and conclusion.
- For a sum, the inductive step adds the next term: , then factorise.
- For divisibility, show is a multiple of , or substitute the assumed form.
- For matrix powers, test , then calculate and check every entry.
- The full conclusion names the basis, the implication and the range of .
The structure of a proof
Induction proves P(n) for every positive integer n: show it is true for n = 1, then that truth for k forces truth for k + 1.
Each of the four parts earns marks. The basis substitutes into both sides. The assumption is that is true for some positive integer . The inductive step must use the assumption; proving from scratch is not induction.
- 1
Basis
show is true
- 2
Assumption
assume is true
- 3
Inductive step
show is true using
- 4
Conclusion
true for all positive integers
Which part of the proof is missing if you only show that true implies true?
Summation of series
Add the next term to the assumed sum, then factorise to reach the formula with n = k + 1.
The same method proves : add and factorise out to get .
- Sum to terms
Worked example
Prove .
- 1
Basis: for the sum is and the formula gives . True for .
- 2
Assume true for : .
- 3
Add the next term: the sum to terms is .
- 4
Factorise: , the formula with .
Going from to terms in , which term do you add?
Divisibility
Show f(1) is a multiple of d, assume f(k) is a multiple, then write f(k+1) as a multiple of d.
Two reliable routes: form (or ) and show it is a multiple of ; or substitute the assumed form, e.g. , directly into .
- 1
Basis
is a multiple of
- 2
Assume
- 3
Difference
is a multiple of
- 4
Conclude
is a sum of two multiples of
Worked example
Prove that is divisible by 4.
- 1
Basis: , which is a multiple of 4.
- 2
Assume is divisible by 4.
- 3
, a multiple of 4.
- 4
So is a multiple of 4.
If is a multiple of and is a multiple of , what follows?
Powers of matrices
Test n = 1, assume the formula for k, then calculate M^k M and match every entry to the formula with k + 1.
Matrix multiplication is not commutative in general, but , so either order is acceptable here.
- 1
Basis
formula at n = 1 equals M
- 2
Assume true for n = k
- 3
Step
M^(k+1) = M^k M, so the formula holds for k + 1
- 4
Conclusion
true for all positive integers n
- Basisformula at equals
- Step
Worked example
For , prove .
- 1
Basis: for the formula gives .
- 2
Assume .
- 3
. The top-left entry is , as required.
- 4
Check the other entries: top-right , bottom-left , bottom-right .
What must the formula give when ?
Writing the conclusion
A mark is awarded for naming the basis, the implication and the range of n.
A model sentence: 'The statement is true for , and if it is true for then it is true for . Therefore it is true for all positive integers by mathematical induction.'
In a 'show that' step, write the expression for , substitute the assumption, simplify, and state that this is the required form. If the question starts from or another value, use that as the basis and amend the final sentence.
- 1
Name the basis
true for n = 1
- 2
Name the implication
true for n = k gives true for n = k + 1
- 3
State the conclusion
true for all positive integers n by mathematical induction
Full conclusion
- Names the basis
- Names the implication
- States all positive integers n
Not enough
- 'So it is true for all n.'
- 'Hence proved.'
- No mention of the basis
Which conclusion earns the mark?
Try an exam question
Prove by induction that for all positive integers .
[4 marks]
- [1]Basis: for the sum is and , so true for .
- [1]Assume true for : .
- [1]Then , the formula with .
- [1]True for , and true for implies true for , so true for all positive integers by induction.
That's the notes covered.
Carry on to the next subtopic.
Try a question
What is the value of each side of the identity when ?
1 mark, marked against the mark scheme
What is the value of each side of the identity when ?
1 mark, marked against the mark scheme