Proof by mathematical induction
Studying this course? Keep your progress in one place.
Key facts
- Four steps: basis, assumption, inductive step, conclusion.
- Assume is true; you must prove , not assume it.
- For series, add the next term to the assumed sum and factorise.
- For divisibility, find to cancel the power.
- Always write the full conclusion sentence.
The four steps
Show is true, assume , prove , then conclude.
To prove a statement for all positive integers , follow four steps.
The idea is a chain: gives , which gives , and so on. The basis starts the chain; the step keeps it going. Without either, the proof is incomplete.
- 1
Basis
show is true, checking both sides of the statement
- 2
Assumption
assume is true for some positive integer
- 3
Inductive step
use the assumption to show is true
- 4
Conclusion
is true and , so is true for all positive integers by mathematical induction
What do you assume in the second step?
Summation of series
Add the next term to the assumed sum, then factorise to reach the formula with .
The step adds the next term to the assumed sum. In the step, factorise out common factors rather than expanding everything.
The same method proves .
- + the th term
Worked example
Prove that for all positive integers .
- 1
Basis, : LHS and RHS . True for .
- 2
Assume true for : .
- 3
Add the next term: .
- 4
Factorise: .
- 5
This is the formula with .
- 6
True for , and true for true for , so true for all positive integers by induction.
In proving a sum formula, what do you add to the assumed ?
Divisibility
Show is divisible by , assume is, then write using .
To prove is divisible by : show is divisible by , assume , and then express using .
Look for where is chosen to cancel the power; the remainder should be a constant multiple of .
- 1
Basis
show f(1) is divisible by m
- 2
Assume
f(k) = m × integer
- 3
Step
write f(k+1) − a f(k) to cancel the power; the remainder is a multiple of m
- 4
Conclude
true for n = 1, and for k+1 whenever true for k, so true for all positive integers n
- constant multiple of
Worked example
Prove that is divisible by .
- 1
Basis: , which is divisible by .
- 2
Assume is divisible by .
- 3
Then .
- 4
So . Both terms are multiples of , so is divisible by .
- 5
True for and true for true for , so true for all positive integers .
For divisible by 4, what is ?
General terms of a sequence
Substitute the assumed formula for into the recurrence to get .
If a sequence is defined by with given, a formula for is proved by induction.
The step always substitutes the assumed formula for in the recurrence.
- 1
Basis
check the formula against
- 2
Assume
equals the formula
- 3
Step
put it into
- 4
Conclude
formula holds for
Worked example
with . Prove that .
- 1
Basis, : . True.
- 2
Assume .
- 3
Then .
- 4
This is the formula with , so by induction it holds for all positive integers .
For with , what is claimed to be if at ?
Matrix powers
Write and multiply, showing all four entries.
For a matrix , a formula for is proved by writing and multiplying.
Always show all four entries, and compare with the formula with replaced by .
Worked example
. Prove that .
- 1
Basis, : . True.
- 2
Assume .
- 3
Then .
- 4
This is the formula with , so by induction it holds for all positive integers .
In the matrix induction step, which product do you evaluate?
Try an exam question
Prove by induction that for all positive integers .
[4 marks]
- [1]Basis: for , LHS and RHS .
- [1]Assumes true for and adds .
- [1]Factorises: , the formula with .
- [1]Conclusion: true for and , so true for all positive integers by induction.
That's the notes covered.
Carry on to the next subtopic.
Try a question
In the inductive step, the student assumes that the result is true for . What must the student then show?
1 mark, marked against the mark scheme
In the inductive step, the student assumes that the result is true for . What must the student then show?
1 mark, marked against the mark scheme