Induction for divisibility and matrix powers
Studying this course? Keep your progress in one place.
Key facts
- For divisibility, write the hypothesis as an equation: for some integer .
- The step must end with .
- Two methods: the difference , or substituting for the power using the hypothesis.
- For matrices, assume equals the formula, then use and check every entry.
- Never drop the full conclusion: basis, , so true for all positive integers .
Setting up divisibility
Write the hypothesis as an equation with an unknown integer multiple, so you have something to substitute.
To prove is divisible by for all positive integers :
- Basis: show is a multiple of .
- Hypothesis: assume for some integer .
- Step: show .
‘Assume is divisible by ’ on its own gives you nothing to use. The multiple is an integer multiple, which may be any whole number.
- 1
Basis
is a multiple of
- 2
Hypothesis
, an integer
- 3
Step
- 4
Conclusion
true for and , so true for all positive integers
Assume is divisible by . Which hypothesis is correctly written?
Two ways to finish
Either show the difference is a multiple of , or substitute for the power from the hypothesis.
Method 1: the difference. Show is a multiple of . Then .
Method 2: substitute. Rewrite the power using the hypothesis, for example , so .
Useful differences: and .
- 1
Assume
for some integer
- 2
Method 1
Show is a multiple of
- 3
Method 2
Substitute the power from the hypothesis
- 4
Conclude
Difference
- Find
- Show it is a multiple of
- Add to
Substitute
- Rearrange the hypothesis for the power
- Replace it in
- Factorise out
Worked example
Prove that is divisible by for all positive integers .
- 1
Basis: : .
- 2
Hypothesis: assume for some integer , so .
- 3
Step: , a multiple of .
- 4
Conclusion: true for , and true for implies true for , so true for all positive integers by induction.
If , which expression equals ?
Polynomial expressions
Find and use the fact that the product of two consecutive integers is always even.
For (divisible by ): .
The product of consecutive integers is always even, so and .
Hence .
State the reason is even: one of two consecutive integers is even.
- always even
Why is always even?
Powers of a matrix
Assume the formula for , multiply by , and show every entry matches the formula with .
To prove a formula for , check , assume equals the formula, then use and multiply the matrices.
Calculate and first to spot the pattern, then prove it. Show that every entry matches (for example ).
- 1
Basis
Check the formula gives when
- 2
Assume
equals the formula
- 3
Multiply
- 4
Match
Every entry equals the formula with
Worked example
. Prove that .
- 1
Basis: gives .
- 2
Hypothesis: assume .
- 3
Step: .
- 4
Conclusion: the result is the formula with , so by induction it is true for all positive integers .
What is for this matrix ?
Presenting the answer
Name the integer expression in a divisibility proof, match every matrix entry, and always give the full conclusion.
For divisibility, the last line must be , naming the integer expression.
For matrices, show that every entry matches the formula with (for example , not just ).
Marks are lost for ‘so true for all ’ without the basis and the inductive link.
- 1
Basis step
Show the result is true for
- 2
Inductive step
Name the integer expression, or match every entry
- 3
Conclusion
True for implies true for , so true for all positive integers
- Divisibility step
- Matrix stepevery entry matches
In a divisibility proof, what should the final line of the inductive step look like?
Try an exam question
Prove by induction that is divisible by for all positive integers .
[4 marks]
- [1]Basis: : , so true for .
- [1]Assume for some integer , so .
- [1], a multiple of .
- [1]Conclusion: 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
Find the value of .
1 mark, marked against the mark scheme
Find the value of .
1 mark, marked against the mark scheme