Induction for series and sequences
Studying this course? Keep your progress in one place.
Key facts
- Induction proves a statement for all positive integers in four stages: basis, hypothesis, step, conclusion.
- In the step you assume only and must deduce .
- For a sum: the sum to terms is the sum to terms plus the th term.
- Write the target first: the formula with every replaced by .
- For a recurrence , substitute the hypothesis for .
- Always finish with the full conclusion: true for , and , so true for all positive integers .
How induction works
If the first case is true and each case forces the next, then every case is true, like a line of dominoes.
Mathematical induction proves a statement for all positive integers .
It works like a line of dominoes: if the first one falls, and each one knocks over the next, they all fall.
Each of the four stages in the diagram must be written down.
- 1
Basis step
show is true
- 2
Inductive hypothesis
assume is true for some positive integer
- 3
Inductive step
using that assumption, show is true
- 4
Conclusion
true and , so is true for all positive integers
In the inductive step, what are you allowed to assume?
Proving a sum formula
Add the th term to the assumed sum to terms, then show the result equals the formula with .
To prove , check both sides when , then assume .
The sum to terms is the sum to terms plus the th term:
Show algebraically that this equals the target .
- Sum to termssum to terms
- Target replace every by
Worked example
Prove that .
- 1
Basis: : LHS , RHS , so true for .
- 2
Hypothesis: assume .
- 3
Step: , the formula with .
- 4
Conclusion: true for , and true for implies true for , so true for all positive integers by induction.
What is the target when ?
Harder algebra in the step
The method is identical; take out the common factor first and the remaining bracket should factorise into the target.
For :
For :
Standard results you may need to prove: and .
- Add
- Take out
- Bracket:
- Add
- Common denominator
- Numerator:
In the proof, what is the bracket after expanding?
Sequences defined by recurrence
Substitute the hypothesis for into the recurrence to get , and show it matches the formula with .
For a sequence with , the hypothesis gives as a formula. Put it into the recurrence relation and simplify.
Before proving, check the first few terms by hand to confirm the formula is right: here and .
- 1
Basis
check against the formula
- 2
Hypothesis
assume equals the formula
- 3
Step
put it into and simplify
- 4
Conclusion
state it for all positive integers
Worked example
and . Prove that .
- 1
Basis: .
- 2
Hypothesis: assume .
- 3
Step: , the formula with .
- 4
Conclusion: true for and , so true for all positive integers by induction.
If , what is ?
Writing the conclusion
The conclusion must link the basis step and the inductive step; a vague one loses marks.
Write:
‘The result is true for . If it is true for , then it is true for . Therefore, by mathematical induction, it is true for all positive integers .’
Show the basis step with both sides evaluated, and state the inductive hypothesis explicitly.
- true and true for all positive integers
Which part of a conclusion is essential for full marks?
Try an exam question
Prove by induction that for all positive integers .
[5 marks]
- [1]Basis: , LHS and RHS .
- [1]Assume true for : .
- [1]Add the th term: .
- [1]Factorise to , the formula with .
- [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