Further Mathematical Induction
Induction with base cases above 1 and steps of 2, sums in sigma notation, inequalities such as 2ⁿ > n², divisibility results, and proving formulas for first-order recursive sequences.
60 min · Proof
Assumes you have read Proof by Mathematical Induction and Proving Inequalities.
The full teaching. Start here.
The short version
- Base case: check the smallest in the set, such as for "", or for "even ".
- Hypothesis: assume the result for some in the set. Write it as an equation (for example ) or as an inequality.
- Step: prove it for the next member: , or for even or odd . Use the hypothesis explicitly.
- Conclusion: "by mathematical induction, true for all …".
- Sums: .
- Inequalities: after using the hypothesis, prove a separate small inequality to reach the form.
- Recursions: substitute the hypothesis into .
Adjusting the base case and the step
Induction works like dominoes. The base case knocks over the first domino, and the step shows each domino knocks over the next. Both must match the set of in the claim:
- "for all ": base , step ;
- "for all even ": base , step ;
- "for all odd ": base , step .
Worked example3 marks
Induction over even numbers
Prove that is a multiple of for every even positive integer .
Base case
Smallest even positive integer.
: , a multiple of .
Hypothesis
Some even k.
Assume for some even and integer .
Step to k + 2
The next even number.
. Since is even, for an integer , so the total is .
Answer
True for , and true for implies true for . By induction, true for all even positive integers.
Is that answer sensible?
: . : . The claim fails for odd ( gives ), which is why stepping by is essential.
CheckpointAnswer before reading on.
To prove a statement for all even positive integers n by induction, which structure is correct?
Hint 1Smallest even positive integer.
Hint 2Next even number after k.
Hint 3k to k + 2.
CheckpointAnswer before reading on.
To prove for all integers , what is the base case?
Hint 1Smallest n in the set.
Hint 2n > 4.
Hint 3n = 5.
Exam question
Standard · about 5 min
3 marks
Prove by induction that is divisible by for all odd positive integers .
Hint 1Base n = 1.
Hint 2Step k to k + 2.
Hint 3.
Where students lose marks on this one
Stepping to k + 1.
Why it happens: Wrong step size.
Odd numbers go up by 2.
Written for this site.
Sigma notation
means . The letter is a dummy index, and is the upper limit. The key identity for induction is
so the step always adds exactly one new term.
Worked example3 marks
A sum in sigma notation
Prove that for all positive integers .
Base case
N = 1.
LHS and RHS .
Add the next term
Assume true for N = k.
.
Factorise
Aim for (k + 1)/(2k + 3).
, so the sum is .
Answer
By induction, the formula holds for all positive integers .
Is that answer sensible?
: , and matches.
CheckpointAnswer before reading on.
Evaluate .
Hint 1Substitute r = 1, 2, 3, 4.
Hint 21 + 4 + 9 + 16.
Hint 330.
CheckpointAnswer before reading on.
Which is in sigma notation?
Hint 1General term.
Hint 2r-th term r(r + 1).
Hint 3r from 1 to n.
Exam question
Standard · about 5 min
3 marks
Prove by induction that for all positive integers .
Hint 1Base n = 1: 2 = 2.
Hint 2Add (k + 1)(k + 2).
Hint 3Factor (k + 1)(k + 2).
Where students lose marks on this one
Expanding everything into a cubic.
Why it happens: Making algebra harder.
Factor out (k + 1)(k + 2) first.
Written for this site.
Exam question
Standard · about 5 min
3 marks
Prove by induction that for all positive integers .
Hint 1Base: 1/2.
Hint 2Add .
Hint 3Numerator .
Where students lose marks on this one
Adding 1/(k(k + 1)) as the new term.
Why it happens: Wrong next term.
Replace r by k + 1.
Written for this site.
Exam question
Standard · about 5 min
3 marks
Prove by induction that .
Hint 1Base: 1 = 1.
Hint 2Factor .
Hint 3.
Where students lose marks on this one
Expanding to degree 4.
Why it happens: Messy algebra.
Factor (k + 1)² first.
Written for this site.
Exam question
Harder · about 5 min
3 marks
Prove by induction that for all positive integers .
Hint 1Base: 2 = 0 + 2.
Hint 2Add .
Hint 3.
Where students lose marks on this one
Writing 2k·2^(k + 1) = k·2^(2k + 2).
Why it happens: Index law error.
2 × 2^(k + 1) = 2^(k + 2).
Written for this site.
Exam question
Standard · about 5 min
3 marks
Prove by induction that .
Hint 1Base: 1 = 2 − 1.
Hint 2Add .
Hint 3.
Where students lose marks on this one
Writing (k + 1)(k + 1)! = (k + 2)!.
Why it happens: Factorial error.
(k + 2)! = (k + 2)(k + 1)!.
Written for this site.
Inequalities
Inequality steps rarely land exactly on the target. Typically you use the hypothesis to get , and then prove separately that .
Worked example4 marks
An inequality by induction
Prove that for all integers .
Base case
The smallest integer greater than 4.
: .
Use the hypothesis
Assume 2ᵏ > k² for some k ≥ 5.
.
Bridge to (k + 1)²
Show 2k² ≥ (k + 1)².
for .
Combine
Chain the two inequalities.
.
Answer
By induction, for all integers .
Is that answer sensible?
The bridge needs , true for , but the base case at fails (). So both parts are needed, and the result really does start at .
CheckpointAnswer before reading on.
In proving for integers , what is the correct inductive hypothesis?
Hint 1Assume for some k in the set.
Hint 2Not for all k.
Hint 3k ≥ 5.
Exam question
Standard · about 5 min
3 marks
Prove by induction that for all integers .
Hint 1Base: 24 > 16.
Hint 2.
Hint 3.
Where students lose marks on this one
Base case n = 1.
Why it happens: The claim is false for n = 1, 2, 3.
Start where the statement begins.
Written for this site.
Exam question
Harder · about 5 min
3 marks
Prove by induction that for all positive integers and all real .
Hint 1Base n = 1: equality.
Hint 2Multiply by 1 + x > 0.
Hint 3Drop .
Where students lose marks on this one
Multiplying by (1 + x) without noting 1 + x > 0.
Why it happens: Missing the condition.
That is exactly why x > −1 is needed.
Written for this site.
Exam question
Harder · about 6 min
4 marks
Prove by induction that for all integers .
Hint 1Base: 81 > 64.
Hint 2.
Hint 3For : , .
Where students lose marks on this one
Stopping at 3^(k + 1) > 3k³ without comparing to (k + 1)³.
Why it happens: Incomplete step.
You must reach (k + 1)³.
Written for this site.
Exam question
Harder · about 6 min
4 marks
Prove by induction that for all positive integers .
Hint 1Base: 1 ≤ 1.
Hint 2Need .
Hint 3Reduces to .
Where students lose marks on this one
Starting from the required inequality and "proving" it.
Why it happens: Working backwards without reversibility.
Show the needed inequality holds, with reversible steps.
Written for this site.
Divisibility
Write the hypothesis as an equation, such as , and rewrite in terms of .
Worked example3 marks
A divisibility proof
Prove that is divisible by for all positive integers .
Base case
n = 1.
.
Hypothesis as an equation
Makes substitution possible.
Assume , so .
Step
n = k + 1.
.
Answer
Divisible by for , so by induction for all positive integers .
Is that answer sensible?
: .
CheckpointAnswer before reading on.
In proving by induction, how is the inductive hypothesis best written?
Hint 1Divisible means equals 7 × integer.
Hint 2Introduce M.
Hint 3.
Exam question
Standard · about 4 min
3 marks
Prove by induction that is divisible by for all positive integers .
Hint 1Base: 7.
Hint 2.
Hint 3.
Where students lose marks on this one
Writing 2^(3k + 3) = 2^(3k) + 8.
Why it happens: Index law error.
2^(3k + 3) = 2^(3k) × 2³.
Written for this site.
Exam question
Standard · about 5 min
3 marks
Prove by induction that is divisible by for all positive integers .
Hint 1Base: 27.
Hint 2.
Hint 3.
Where students lose marks on this one
Not splitting off the hypothesis.
Why it happens: Not using the assumption.
Rewrite to include 5^k + 2·11^k.
Written for this site.
Recursive formulae
A first-order recursion gives each term from the one before, as in with . Induction proves a closed formula: check the first term, then substitute the hypothesis for into the recursion.
Worked example3 marks
Proving a formula for a recursion
A sequence has and . Prove that for all .
Base case
First term.
.
Step
Assume a_k = 2ᵏ − 1 and use the recursion.
.
Answer
By induction, for all .
Is that answer sensible?
Terms from the recursion: . The formula gives .
CheckpointAnswer before reading on.
A sequence has and . Find .
Hint 1Generate terms.
Hint 21, 3, 7, …
Hint 315.
Exam question
Standard · about 4 min
3 marks
A sequence has and . Prove by induction that .
Hint 1Base: 3⁰ + 1 = 2.
Hint 2Substitute the hypothesis into the recursion.
Hint 3.
Where students lose marks on this one
Checking the first few terms only.
Why it happens: Using examples.
Induction proves it for all n.
Written for this site.
Exam question
Standard · about 4 min
3 marks
A sequence has and . Prove by induction that .
Hint 1Base: a₁ = 1.
Hint 2.
Hint 3Multiply top and bottom by k.
Where students lose marks on this one
Writing (1/k)/(1 + 1/k) = 1/(1 + k²).
Why it happens: Fraction error.
Multiply numerator and denominator by k.
Written for this site.
Why both parts matter
CheckpointAnswer before reading on.
A student "proves" that is even for all positive integers : if is even, then is even. What is wrong?
Hint 1Check n = 1.
Hint 23 is odd.
Hint 3The base case fails.
CheckpointAnswer before reading on.
"All horses are the same colour": for n horses, remove one to get n − 1 of the same colour, remove another to get another n − 1 of the same colour, and the overlap forces all n to match. Where does this fail?
Hint 1Try n = 2.
Hint 2Overlap size n − 2.
Hint 3Zero overlap.
Common mistake
Assume 2ᵏ > k². Then 2ᵏ⁺¹ > (k + 1)². Check: 2·2ᵏ > k² + 2k + 1, which is true because 2ᵏ > k².
Why it happens: This writes down the goal and then asserts it, rather than deriving it.
Start from the left side, , apply the hypothesis to get , and then prove the bridge with the condition . Every inequality sign in the chain needs a reason.
What lifts this to a Band 6
In the step, write "RTP:" (required to prove) followed by the exact statement for before you start. Then write your working as one chain starting from the left side, and mark where the hypothesis is used ("by the inductive hypothesis"). Markers look for that explicit use of the hypothesis, and the RTP line stops you aiming at the wrong target.
Strong induction
Some recursions depend on two earlier terms, such as the Fibonacci sequence . Proving needs two base cases ( and ) and a hypothesis covering both and : then . This is strong induction: you may assume the result for every value up to . It is no more powerful logically, but it is often more convenient.