Home / A-Level Further Maths 9231 / Proof by induction / Proof by induction: sums and sequences
Cambridge International AS & A Level · Topic 1.7
A-Level Further Maths 9231 / Topic 1.7 / AS & A Level

Knock over the first, and every one falls.

Proof by induction proves a statement for every positive integer \(n\) in two moves: show it is true for \(n = 1\), then show that whenever it is true for \(n = k\) it must be true for \(n = k + 1\). Four parts, each one marked, and a conclusion sentence written out in full.

Topic 1.7All proof by induction lessons →
The key idea

To prove a statement \(P(n)\) for all positive integers \(n\): (1) base case: show \(P(1)\) is true; (2) assumption: assume \(P(k)\) is true for some positive integer \(k\); (3) inductive step: write down the target \(P(k + 1)\), then reach it using the assumption; (4) conclusion: 'The result is true for \(n = 1\), and if it is true for \(n = k\) then it is true for \(n = k + 1\). Hence, by induction, it is true for all positive integers \(n\).'

… … n = 1 n = 2 n = 3 k k + 1 base case: true for n = 1 inductive step: true for k ⇒ true for k + 1 Together: every domino falls, so the result holds for all n ≥ 1
Fig. 1: induction as a row of dominoes. The base case knocks over the first; the inductive step guarantees that whenever domino k falls, domino k + 1 falls too. Neither part works without the other
Section 01

Four parts, every time.

An induction proof has a fixed shape, and Cambridge mark schemes give a mark for each part. Learn the shape once and use it for sums, sequences, divisibility and matrices alike. The key move is the inductive step: you do not prove \(P(k)\); you ASSUME it and use it to prove \(P(k + 1)\).

PartWhat you write
Base caseWhen \(n = 1\): work out the left side and the right side separately and show they are equal.
AssumptionAssume the result is true for \(n = k\), for some positive integer \(k\); write it out in full with \(k\).
Inductive stepWrite the target (the result with \(n = k + 1\)), then start from the left side for \(n = k + 1\), use the assumption, and reach the target.
Conclusion'The result is true for \(n = 1\), and if it is true for \(n = k\) then it is true for \(n = k + 1\). Hence, by induction, it is true for all positive integers \(n\).'

For a sum, the step always starts the same way: \(\displaystyle\sum_{r=1}^{k+1} u_r = \sum_{r=1}^{k} u_r + u_{k+1}\). The first piece is replaced by the assumption; the second is the \((k + 1)\)th term.

Worked example The shape on a simple sum
Prove by induction that \(\displaystyle\sum_{r=1}^{n} (2r - 1) = n^{2}\) for all positive integers \(n\).
  1. Base case. When \(n = 1\): LHS \(= 2(1) - 1 = 1\), RHS \(= 1^{2} = 1\). So the result is true for \(n = 1\).
  2. Assumption. Assume the result is true for \(n = k\): \(\displaystyle\sum_{r=1}^{k} (2r - 1) = k^{2}\).
  3. Target. For \(n = k + 1\) we want \(\displaystyle\sum_{r=1}^{k+1} (2r - 1) = (k + 1)^{2}\).
  4. Step. \(\displaystyle\sum_{r=1}^{k+1} (2r - 1) = \sum_{r=1}^{k} (2r - 1) + \big(2(k + 1) - 1\big) = k^{2} + 2k + 1 = (k + 1)^{2}\).
  5. Conclusion. The result is true for \(n = 1\), and if it is true for \(n = k\) then it is true for \(n = k + 1\). Hence, by induction, it is true for all positive integers \(n\).
Answer: \(\displaystyle\sum_{r=1}^{n} (2r - 1) = n^{2}\) for all positive integers \(n\)
Worked example Factorise towards the target
Prove by induction that \(\displaystyle\sum_{r=1}^{n} r(r + 1) = \tfrac{1}{3}n(n + 1)(n + 2)\) for all positive integers \(n\).
  1. Base case. When \(n = 1\): LHS \(= 1 \times 2 = 2\), RHS \(= \tfrac{1}{3}(1)(2)(3) = 2\). True for \(n = 1\).
  2. Assumption. Assume \(\displaystyle\sum_{r=1}^{k} r(r + 1) = \tfrac{1}{3}k(k + 1)(k + 2)\).
  3. Target. \(\displaystyle\sum_{r=1}^{k+1} r(r + 1) = \tfrac{1}{3}(k + 1)(k + 2)(k + 3)\).
  4. Step. \(\displaystyle\sum_{r=1}^{k+1} r(r + 1) = \tfrac{1}{3}k(k + 1)(k + 2) + (k + 1)(k + 2)\). The target has the factor \((k + 1)(k + 2)\), so take it out rather than expanding: \(= \tfrac{1}{3}(k + 1)(k + 2)(k + 3)\).
  5. Conclusion. True for \(n = 1\); if true for \(n = k\) then true for \(n = k + 1\). Hence, by induction, true for all positive integers \(n\).
Answer: \(\displaystyle\sum_{r=1}^{n} r(r + 1) = \tfrac{1}{3}n(n + 1)(n + 2)\), as required
Your turn
You are proving \(\displaystyle\sum_{r=1}^{n} r^{2} = \tfrac{1}{6}n(n + 1)(2n + 1)\) by induction. Write down the target statement for \(n = k + 1\), and the term you add to the assumed sum.
Examiner trap

Never write 'assume true for all \(n\)' or 'assume true for \(n = k + 1\)': that assumes what you are proving and scores nothing. Assume only \(P(k)\). And never stop at 'so true for \(n = k + 1\)': without the full conclusion sentence, naming both the base case and the step, the final mark is lost.

Section 02

Sums that need factorising.

The harder the sum, the more the step depends on algebra. The golden rule: look at the target first and keep its factors in view. Combine fractions over a common denominator and factorise the numerator; with factorials, take out the common factorial. The classic \(\displaystyle\sum_{r=1}^{n} r^{3} = \tfrac{1}{4}n^{2}(n + 1)^{2}\) works the same way: take out \((k + 1)^{2}\) and the bracket left over is \((k + 2)^{2}\).

Worked example A fraction sum
Prove by induction that \(\displaystyle\sum_{r=1}^{n} \dfrac{1}{r(r + 1)} = \dfrac{n}{n + 1}\) for all positive integers \(n\).
  1. Base case. When \(n = 1\): LHS \(= \dfrac{1}{1 \times 2} = \dfrac{1}{2}\), RHS \(= \dfrac{1}{2}\). True for \(n = 1\).
  2. Assumption. Assume \(\displaystyle\sum_{r=1}^{k} \dfrac{1}{r(r + 1)} = \dfrac{k}{k + 1}\).
  3. Target. \(\displaystyle\sum_{r=1}^{k+1} \dfrac{1}{r(r + 1)} = \dfrac{k + 1}{k + 2}\).
  4. Step. \(\displaystyle\sum_{r=1}^{k+1} \dfrac{1}{r(r + 1)} = \dfrac{k}{k + 1} + \dfrac{1}{(k + 1)(k + 2)} = \dfrac{k(k + 2) + 1}{(k + 1)(k + 2)} = \dfrac{k^{2} + 2k + 1}{(k + 1)(k + 2)}\).
  5. \(= \dfrac{(k + 1)^{2}}{(k + 1)(k + 2)} = \dfrac{k + 1}{k + 2}\), which is the target.
  6. Conclusion. True for \(n = 1\); if true for \(n = k\) then true for \(n = k + 1\). Hence, by induction, true for all positive integers \(n\).
Answer: \(\displaystyle\sum_{r=1}^{n} \dfrac{1}{r(r + 1)} = \dfrac{n}{n + 1}\), as required
Worked example A factorial sum
Prove by induction that \(\displaystyle\sum_{r=1}^{n} r \times r! = (n + 1)! - 1\) for all positive integers \(n\).
  1. Base case. When \(n = 1\): LHS \(= 1 \times 1! = 1\), RHS \(= 2! - 1 = 1\). True for \(n = 1\).
  2. Assumption. Assume \(\displaystyle\sum_{r=1}^{k} r \times r! = (k + 1)! - 1\).
  3. Target. \(\displaystyle\sum_{r=1}^{k+1} r \times r! = (k + 2)! - 1\).
  4. Step. \(\displaystyle\sum_{r=1}^{k+1} r \times r! = (k + 1)! - 1 + (k + 1)(k + 1)! = (k + 1)!\,\big(1 + (k + 1)\big) - 1\).
  5. \(= (k + 2)(k + 1)! - 1 = (k + 2)! - 1\), which is the target.
  6. Conclusion. True for \(n = 1\); if true for \(n = k\) then true for \(n = k + 1\). Hence, by induction, true for all positive integers \(n\).
Answer: \(\displaystyle\sum_{r=1}^{n} r \times r! = (n + 1)! - 1\), as required
Your turn
Prove by induction that \(\displaystyle\sum_{r=1}^{n} \dfrac{1}{(r + 1)(r + 2)} = \dfrac{n}{2(n + 2)}\) for all positive integers \(n\).
Examiner trap

The \((k + 1)\)th term is found by putting \(r = k + 1\) into the GENERAL TERM, not into the formula for the sum: for \(\sum \dfrac{1}{r(r + 1)}\) it is \(\dfrac{1}{(k + 1)(k + 2)}\), not \(\dfrac{k + 1}{k + 2}\). And resist expanding everything into a cubic or quartic: factorising with the target in view is shorter and far less error-prone.

Stage 1 · Learn

Check your understanding

Four quick checks. Each correct answer earns XP and records this skill on your profile.

Quick check+10 XP

In a proof by induction, what does the inductive step show?

Quick check+10 XP

You are proving \(\displaystyle\sum_{r=1}^{n} r^{3} = \tfrac{1}{4}n^{2}(n + 1)^{2}\). What is the target for \(n = k + 1\)?

Quick check+10 XP

Proving \(\displaystyle\sum_{r=1}^{n} \dfrac{1}{r(r + 1)} = \dfrac{n}{n + 1}\), what do you add to \(\dfrac{k}{k + 1}\) in the step?

Quick check+10 XP

For \(u_1 = 1\), \(u_{n+1} = 2u_n + 1\), assume \(u_k = 2^{k} - 1\). What does the recurrence give for \(u_{k+1}\)?

Section 03

Sequences from a recurrence.

A sequence may be defined by its first term and a rule linking each term to the one before, such as \(u_{n+1} = 2u_n + 1\). Induction proves a closed form \(u_n = \dots\) for every \(n\). The base case checks the formula against the given \(u_1\); the step uses the RECURRENCE to build \(u_{k+1}\) from the assumed \(u_k\).

The step for a sequence always has three moves: start from \(u_{k+1} = \text{(recurrence applied to } u_k\text{)}\), substitute the assumed formula for \(u_k\), and simplify to the formula with \(n = k + 1\). The next lesson shows how to find such a formula yourself from the first few terms before proving it.

Worked example A linear recurrence
The sequence \(u_1, u_2, u_3, \dots\) is defined by \(u_1 = 1\) and \(u_{n+1} = 2u_n + 1\) for \(n \ge 1\). Prove by induction that \(u_n = 2^{n} - 1\) for all positive integers \(n\).
  1. Base case. When \(n = 1\): \(2^{1} - 1 = 1 = u_1\). True for \(n = 1\).
  2. Assumption. Assume \(u_k = 2^{k} - 1\) for some positive integer \(k\).
  3. Target. \(u_{k+1} = 2^{k + 1} - 1\).
  4. Step. By the recurrence, \(u_{k+1} = 2u_k + 1 = 2(2^{k} - 1) + 1 = 2^{k + 1} - 2 + 1 = 2^{k + 1} - 1\).
  5. Conclusion. True for \(n = 1\); if true for \(n = k\) then true for \(n = k + 1\). Hence, by induction, \(u_n = 2^{n} - 1\) for all positive integers \(n\).
Answer: \(u_n = 2^{n} - 1\) for all positive integers \(n\)
Worked example A fraction recurrence
A sequence is defined by \(u_1 = \tfrac{1}{2}\) and \(u_{n+1} = \dfrac{u_n}{1 + u_n}\). Prove by induction that \(u_n = \dfrac{1}{n + 1}\) for all positive integers \(n\).
  1. Base case. When \(n = 1\): \(\dfrac{1}{1 + 1} = \dfrac{1}{2} = u_1\). True for \(n = 1\).
  2. Assumption. Assume \(u_k = \dfrac{1}{k + 1}\).
  3. Target. \(u_{k+1} = \dfrac{1}{k + 2}\).
  4. Step. \(u_{k+1} = \dfrac{u_k}{1 + u_k} = \dfrac{\frac{1}{k + 1}}{1 + \frac{1}{k + 1}} = \dfrac{\frac{1}{k + 1}}{\frac{k + 2}{k + 1}} = \dfrac{1}{k + 2}\).
  5. Conclusion. True for \(n = 1\); if true for \(n = k\) then true for \(n = k + 1\). Hence, by induction, \(u_n = \dfrac{1}{n + 1}\) for all positive integers \(n\).
Answer: \(u_n = \dfrac{1}{n + 1}\) for all positive integers \(n\)
Your turn
A sequence has \(u_1 = 1\) and \(u_{n+1} = 3u_n + 2\). Prove by induction that \(u_n = 2 \times 3^{n - 1} - 1\).
Examiner trap

In the step, \(u_{k+1}\) must come from the recurrence. Writing '\(u_{k+1} = 2^{k + 1} - 1\)' straight from the formula assumes the result for \(n = k + 1\), which is the thing you are proving. Also check the base case against the \(u_1\) the question gives: a formula can satisfy the step yet start at the wrong value.

Stage 2 · Exam

Exam-style questions

Unlocks once the four checks above are done. Worth more XP, written to AS & A Level Further Mathematics Paper 1 to 4 standard.

Finish the four checks above to unlock the exam questions
Exam style+20 XP

In proving \(\displaystyle\sum_{r=1}^{n} r \times r! = (n + 1)! - 1\), a student reaches \((k + 1)! - 1 + (k + 1)(k + 1)!\). This simplifies to

Exam style+20 XP

Which conclusion earns the final mark in an induction proof?

Exam style+20 XP

A sequence has \(u_1 = 2\) and \(u_{n+1} = 3u_n - 2\). Which formula for \(u_n\) could be proved by induction?

Exam style+20 XP

For the statement \(\displaystyle\sum_{r=1}^{n} r = \tfrac{1}{2}(n^{2} + n + 2)\), the inductive step works. Which is true?

Skill unlocked

Base case, assumption, step, conclusion: every domino down.

This skill is now recorded on your profile. Keep the chain going.

-Rank -Level -Score -Topics
Go deeper · practice
Six original Cambridge-style questions
Model induction proofs for an arithmetic sum, a product sum, a fraction sum, a sum with powers of 2, a recurrence-defined sequence and a factorial sum with a deduction.