On this page
Loading guide controls…
Continue lessonNew guided lessons are not available yet.
Guided lesson options
You stopped at:
ContinueRevision Mode is on. Questions and activities are hidden.
The linked question or activity is hidden by Revision Mode.
Mathematical induction proves a statement for every positive integer by proving two finite things: that it holds for a starting value, and that whenever it holds for one integer it holds for the next. This lesson explains why that is enough, writes complete induction proofs for sums, divisibility and inequalities, chooses the right starting value, uses strong induction when a case depends on more than the previous one, finds the gap in a flawed induction, and shows why strengthening a statement can make it easier to prove.
Why induction proves infinitely many cases
Let P(n) be a statement about integers n ≥ n₀. Mathematical induction proves every P(n) from two facts:
- Base case: P(n₀) is true.
- Inductive step: for every integer k ≥ n₀, if P(k) is true then P(k + 1) is true.
Why this is enough: suppose some P(n) were false. Among the integers n ≥ n₀ with P(n) false, take the least one, m. It is not n₀, by the base case, so m-1 ≥ n₀ and P(m-1) is true, because m was the least failure. The inductive step with k = m-1 then makes P(m) true, a contradiction.
In the inductive step, P(k) is an assumption used to prove P(k + 1). You are not assuming what you want to prove: you are proving a conditional, which is valid for every k ≥ n₀.
Worked example 1
A factorial sum
Worked example 1
A factorial sum
Prove that, for every positive integer n,
Show full solutionHide solution
State P(n) and check the base case
Method
Let P(n) be the statement ∑ᵣ₌₁ⁿ r · r! = (n + 1)!-1.Reason
Naming the statement makes clear what is assumed and what must be shown.Working
Answer
For n = 1: the left side is 1 · 1! = 1 and the right side is 2!-1 = 1. So P(1) is true.
Assume P(k) and prove P(k + 1)
Method
Split off the last term of the (k + 1) sum.Reason
The remaining sum is exactly the one that P(k) describes.Working
Answer
Assume P(k) for some positive integer k. Then
∑ᵣ₌₁^(k + 1) r · r! = [(k + 1)!-1] + (k + 1)(k + 1)!; = (k + 1)! (1 + k + 1)-1; = (k + 2)!-1,which is P(k + 1).
Conclude
Working
Answer
P(1) is true, and P(k) ⇒ P(k + 1) for every positive integer k. By mathematical induction, P(n) is true for every positive integer n. blacksquare
Quick check
Check n = 3 directly: 1 + 4 + 18 = 23 = 4!-1. The conclusion should name both parts of the argument; “therefore true by induction” after only a base case is not a proof.
Guided practice 1
A divisibility statement
Guided practice 1
A divisibility statement
Prove that 3²ⁿ⁺¹ + 2ⁿ⁺² is divisible by 7 for every integer n ≥ 0.
Write your answer, then compare it with the solution
Hint 1
Factor the next case
3^(2k + 3) = 9 · 3^(2k + 1) and 2^(k + 3) = 2 · 2^(k + 2). Write 9 as 2 + 7.
Show full solutionHide solution
Base case
Reason
The statement starts at n = 0.Working
Answer
For n = 0: 3¹ + 2² = 7, which is divisible by 7.
Inductive step
Method
Assume 3^(2k + 1) + 2^(k + 2) = 7m for some integer m, where k ≥ 0.Reason
Rewriting the next expression as a multiple of the assumed one plus a multiple of 7 uses the assumption directly.Working
Answer
3^(2k + 3) + 2^(k + 3) = 9 · 3^(2k + 1) + 2 · 2^(k + 2); = 2(3^(2k + 1) + 2^(k + 2)) + 7 · 3^(2k + 1); = 7(2m + 3^(2k + 1)),which is divisible by 7.
Conclude
Working
Answer
The statement is true for n = 0, and its truth for n = k implies its truth for n = k + 1. By induction it holds for every integer n ≥ 0. blacksquare
Quick check
At n = 1 the expression is 27 + 8 = 35 = 7 × 5. Writing the assumption as “3^(2k + 1) + 2^(k + 2) = 7m” with an integer m is what lets the final bracket be recognised as an integer.
The starting value matters
2ⁿ > n² is true for n = 1 (2 > 1) but false for n = 2, 3 and 4 (4 = 4, 8 < 9, 16 = 16). It is true for every n ≥ 5, and induction shows this with base case n = 5, where 32 > 25.
For the inductive step, assume 2^k > k² with k ≥ 5. Then 2^(k + 1) = 2 · 2^k > 2k², and it remains to show 2k² ≥ (k + 1)²:
So 2^(k + 1) > (k + 1)². The base case and the restriction k ≥ 5 work together: the step itself is valid from k = 3, but the chain has to start at a true case.
Strong induction uses any earlier case
In strong induction, the inductive step may assume P(n₀),P(n₀ + 1),…,P(k), all at once, to prove P(k + 1). If the step reaches back j places, you need j base cases so that the first uses of the step have true cases to stand on.
Check your understanding 1
Stamps of 4 and 5 cents
Check your understanding 1
Stamps of 4 and 5 cents
Prove that every whole number of cents n ≥ 12 can be paid exactly using only 4-cent and 5-cent stamps. Which base cases do you need, and why?
Show answerHide answer
Base cases: 12 = 4 + 4 + 4, 13 = 4 + 4 + 5, 14 = 4 + 5 + 5 and 15 = 5 + 5 + 5.
Step: let k ≥ 15 and assume every amount from 12 to k can be paid. Then k + 1-4 = k-3 ≥ 12, so k-3 can be paid, and adding one 4-cent stamp pays k + 1.
The step reaches back four places, so four consecutive base cases are needed: from them, every later amount is reached by adding 4s. The result fails for 11, which is why the statement starts at 12.
Self-mark with the mark scheme
Tick each mark point that your answer includes.
Tick a point only if your written proof contains it. This self-check does not record a mark.
Finding the gap in a flawed induction
Spot the mistake 1
“All counters are the same colour”
Spot the mistake 1
“All counters are the same colour”
Find the error in this argument.
Claim: in every set of n ≥ 1 counters, all the counters are the same colour. Base case: one counter is the same colour as itself. Step: assume every set of k counters is one colour, and take a set of k + 1. Remove the first counter: the other k are one colour. Remove the last counter instead: these k are one colour. The two groups overlap, so all k + 1 counters are the same colour.
Write your answer, then compare it with the solution
Show full solutionHide solution
Test the step at k = 1
Method
Take k = 1, so the set has two counters, A and B.Reason
An inductive step must work for every k ≥ n₀, including the first one.Working
Answer
Removing the first counter leaves {B}; removing the last leaves {A}. These groups do not overlap, so “the two groups overlap” is false and nothing links the colour of A to the colour of B.
Common mistake
The step is correct for every k ≥ 2, where the groups share at least one counter. But the chain needs the link from 1 to 2, and that is exactly the broken one. Checking several large values of k would not reveal the gap; test the smallest k that the step must cover.
Sometimes a stronger statement is easier to prove
Exam-style question 1
A bound on the sum of reciprocal squares
Exam-style question 1
A bound on the sum of reciprocal squares
(a) Prove by induction that, for every positive integer n,
(b) Hence show that ∑ᵣ₌₁ⁿ1/r² < 2 for every positive integer n, and explain why proving this weaker statement directly by induction would not work. [1]
Write your answer, then compare it with the solution
Show full solutionHide solution
Base case
Reason
The statement starts at n = 1.Working
Answer
For n = 1: 1 ≤ 2-1 = 1. True.
Inductive step
Method
Assume ∑ᵣ₌₁^k1/r² ≤ 2-1/k for some positive integer k, and add the next term.Reason
It is then enough to show that 2-1/k + 1/((k + 1)²) ≤ 2-1/(k + 1).Working
Answer
That inequality is equivalent to
1/((k + 1)²) ≤ 1/k-1/(k + 1) = 1/(k(k + 1)),which holds because k(k + 1) ≤ (k + 1)². So ∑ᵣ₌₁^(k + 1)1/r² ≤ 2-1/(k + 1), and by induction (a) holds for every positive integer n.
Deduce the weaker bound
Method
2-1/n < 2 for every positive n.Reason
A direct induction would assume only “the sum is less than 2”, and adding a positive term to a quantity less than 2 can exceed 2.Working
Answer
So ∑ᵣ₌₁ⁿ1/r² ≤ 2-1/n < 2. The stronger statement carries a margin of 1/n that pays for the next term; the weaker one carries no margin.
Self-mark with the mark scheme
Tick each mark point that your answer includes.
Tick a point only if your proof states it. This is a self-check for practice; it does not record a mark or count as evidence.
Common mistake
Starting from the conclusion “∑ᵣ₌₁^(k + 1)1/r² ≤ 2-1/(k + 1)” and working until something true appears is only valid if every step can be reversed. Write the step forwards, or say explicitly that each line is equivalent to the next.
Common mistakes
- Checking several cases and omitting the general inductive step.
- Writing the inductive step as “assume true for all n”, which assumes the result.
- Proving the step from n to n + 1 without actually using the assumption for n.
- Starting the induction at a value where the statement is false, or where the step argument does not yet work.
- Omitting the conclusion that the statement holds for all integers from the starting value onwards.
Loading reading progress…
Lesson done
- Monday
- Tuesday
- Wednesday
- Thursday
- Friday
- Saturday
- Sunday
Checking learning on this device…
Change goal
Progress options
Loading questions…