Proof by mathematical induction
Build a proof from a base case and an induction step, including divisibility and recursively defined sequences.
Exam scope and assessment notes
Mapped to Cambridge International AS & A Level Further Mathematics 9231. These original explanations and self-checks are independent study support, not Cambridge questions, marks or grades. The syllabus assumes prior knowledge of the relevant 9709 Mathematics content; check each component's prerequisites with your teacher. Full-paper assessment and human subject-specialist review remain outstanding.
Before you begin
- Cambridge expects learners to know the whole Cambridge International A Level Mathematics (9709) content. Paper 1 further pure mathematics draws on 9709 Papers 1 and 3. Confirm your exam year and component route with your school.
Work on paper. Try each question before revealing help, and explain why your method works.
Quick readiness check
What makes a Further Mathematics solution convincing?
What you will learn
- Prove a stated result for positive integers by induction
- Use the induction hypothesis to prove the next case
- Use a small numerical trial to form and then verify a conjecture
A complete proof has two linked parts
First prove the statement for the starting value, often n=1. Then assume it holds for n=k and use that assumption to prove it for n=k+1.
State clearly what the induction hypothesis is. The step must derive the next case from the assumed case, not merely check another numerical example.
Divisibility proofs end with an integer multiple
For a divisibility statement, simplify the expression for k+1 and use the hypothesis to isolate a known multiple plus a new multiple of the divisor.
A numerical trial can suggest a claim or pattern, but it cannot establish the claim for every positive integer. The algebraic induction step supplies the general argument.
Pause and explain
Which habit best checks your work on proof by mathematical induction?
Worked example
Prove by induction that 1+3+5+⋯+(2n−1)=n² for n≥1.
Show the worked solution
- Base case n=1: the left side is 1 and the right side is 1.
- Assume the sum through 2k−1 is k². Add the next odd number 2k+1.
- k²+2k+1=(k+1)², which is the required formula for n=k+1.
Answer The base case and induction step prove the result for every positive integer n.
Try a topic test
Choose Easy, Normal or Difficult. Save your answers and open worked review after finishing.
Test this topic →From guided practice to a new situation
Write your answer and reasoning first. Use a hint only if you are stuck. The model solution is for self-checking; your written work is not automatically marked.
Prove by induction that 1+2+⋯+n=n(n+1)/2 for n≥1.
Give me a hint
Check n=1, then add k+1 to the formula assumed for n=k.
Compare my reasoning
- At n=1 both sides are 1.
- Assume the sum through k is k(k+1)/2. Add k+1.
- k(k+1)/2+(k+1)=(k+1)(k+2)/2, the formula for n=k+1.
The statement follows by induction for all n≥1.
Look for these in your work
- Base case verified
- Hypothesis stated
- Next case derived and concluded
Prove that 7ⁿ−1 is divisible by 6 for n≥1.
Give me a hint
Write 7ᵏ as (7ᵏ−1)+1 and use the induction hypothesis.
Compare my reasoning
- For n=1, 7−1=6.
- Assume 7ᵏ−1=6m for an integer m.
- 7ᵏ⁺¹−1=7(7ᵏ−1)+6=42m+6=6(7m+1), an integer multiple of 6.
7ⁿ−1 is divisible by 6 for every positive integer n.
Look for these in your work
- Base case divisible
- Hypothesis represented as 6m
- Next case factorised by 6
A sequence is defined by u₁=2 and uₙ₊₁=3uₙ−2. A learner conjectures uₙ=3ⁿ⁻¹+1. Explain how induction can test and prove the conjecture.
Give me a hint
Substitute the proposed expression into the recurrence after verifying the first term.
Compare my reasoning
- At n=1, 3⁰+1=2, so the base case holds.
- Assume uₖ=3ᵏ⁻¹+1.
- Then uₖ₊₁=3(3ᵏ⁻¹+1)−2=3ᵏ+1, the proposed expression for k+1.
The recurrence and base case prove uₙ=3ⁿ⁻¹+1 for all n≥1.
Look for these in your work
- Base case checked
- Recurrence used with hypothesis
- Next term matches the conjecture
Common mistakes
- Checking several values without proving a general step
- Using the result for k+1 inside the induction step instead of the hypothesis for k
- Failing to state the starting value or conclusion
What can you explain now?
In an induction proof, what must the induction step show?
Compare with the explanation
If the statement is true for k, then it is true for k+1
The base case and this implication together establish the statement for all later integers.
After trying it yourself, choose your next review. This is your self-assessment.
Your review choice appears on Today. Sign in to sync it across devices.
Make it stick
What must be shown in the base case and induction step, and why are numerical trials alone insufficient?
If you needed the solution, close it and solve the problem again from a blank page. A correct answer is stronger when you can explain the reason for each step.