Home · A-Level Further Maths 9231 · Proof by induction · Proof by induction: sums and sequences · Practice
AS & A Level · Practice questions · Proof by induction: sums and sequences

Base, assume, step, conclude.

Six original Cambridge-style proof by induction questions on sums of series and recurrence-defined sequences, each with a model solution laid out the way the mark scheme wants it.

Original questions All questions on this page are original work, written in the Cambridge AS & A Level style. They are not from past papers. They test the same concepts and skills the syllabus rewards.
The method

Four parts, each one written out.

01
Recall
[4 marks]

Prove by induction that \(\displaystyle\sum_{r=1}^{n} (3r - 1) = \tfrac{1}{2}n(3n + 1)\) for all positive integers \(n\).

  • When \(n = 1\): LHS \(= 3 - 1 = 2\), RHS \(= \tfrac{1}{2}(1)(4) = 2\). True for \(n = 1\). ✓
  • Assume true for \(n = k\): \(\displaystyle\sum_{r=1}^{k} (3r - 1) = \tfrac{1}{2}k(3k + 1)\). Target: \(\displaystyle\sum_{r=1}^{k+1} (3r - 1) = \tfrac{1}{2}(k + 1)(3k + 4)\). ✓
  • \(\displaystyle\sum_{r=1}^{k+1} (3r - 1) = \tfrac{1}{2}k(3k + 1) + (3k + 2) = \tfrac{1}{2}(3k^{2} + k + 6k + 4) = \tfrac{1}{2}(3k^{2} + 7k + 4) = \tfrac{1}{2}(k + 1)(3k + 4)\). ✓
  • This is the result for \(n = k + 1\). 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\). ✓
02
Calculation
[5 marks]

Prove by induction that \(\displaystyle\sum_{r=1}^{n} r(r + 1)(r + 2) = \tfrac{1}{4}n(n + 1)(n + 2)(n + 3)\) for all positive integers \(n\).

  • When \(n = 1\): LHS \(= 1 \times 2 \times 3 = 6\), RHS \(= \tfrac{1}{4}(1)(2)(3)(4) = 6\). True for \(n = 1\). ✓
  • Assume \(\displaystyle\sum_{r=1}^{k} r(r + 1)(r + 2) = \tfrac{1}{4}k(k + 1)(k + 2)(k + 3)\). Target: \(\tfrac{1}{4}(k + 1)(k + 2)(k + 3)(k + 4)\). ✓
  • \(\displaystyle\sum_{r=1}^{k+1} r(r + 1)(r + 2) = \tfrac{1}{4}k(k + 1)(k + 2)(k + 3) + (k + 1)(k + 2)(k + 3)\). ✓
  • \(= (k + 1)(k + 2)(k + 3)\left(\tfrac{1}{4}k + 1\right) = \tfrac{1}{4}(k + 1)(k + 2)(k + 3)(k + 4)\), the result for \(n = k + 1\). ✓
  • 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\). ✓
03
Calculation
[5 marks]

Prove by induction that \(\displaystyle\sum_{r=1}^{n} \dfrac{1}{(2r - 1)(2r + 1)} = \dfrac{n}{2n + 1}\) for all positive integers \(n\).

  • When \(n = 1\): LHS \(= \dfrac{1}{1 \times 3} = \dfrac{1}{3}\), RHS \(= \dfrac{1}{3}\). True for \(n = 1\). ✓
  • Assume \(\displaystyle\sum_{r=1}^{k} \dfrac{1}{(2r - 1)(2r + 1)} = \dfrac{k}{2k + 1}\). Target: \(\dfrac{k + 1}{2k + 3}\). The \((k + 1)\)th term is \(\dfrac{1}{(2k + 1)(2k + 3)}\). ✓
  • \(\dfrac{k}{2k + 1} + \dfrac{1}{(2k + 1)(2k + 3)} = \dfrac{k(2k + 3) + 1}{(2k + 1)(2k + 3)} = \dfrac{2k^{2} + 3k + 1}{(2k + 1)(2k + 3)}\). ✓
  • \(= \dfrac{(2k + 1)(k + 1)}{(2k + 1)(2k + 3)} = \dfrac{k + 1}{2k + 3}\), the result for \(n = k + 1\). ✓
  • 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\). ✓
04
Analysis
[5 marks]

Prove by induction that \(\displaystyle\sum_{r=1}^{n} r \times 2^{r - 1} = (n - 1)2^{n} + 1\) for all positive integers \(n\).

  • When \(n = 1\): LHS \(= 1 \times 2^{0} = 1\), RHS \(= 0 \times 2 + 1 = 1\). True for \(n = 1\). ✓
  • Assume \(\displaystyle\sum_{r=1}^{k} r \times 2^{r - 1} = (k - 1)2^{k} + 1\). Target: \(\displaystyle\sum_{r=1}^{k+1} r \times 2^{r - 1} = k \times 2^{k + 1} + 1\). ✓
  • \(\displaystyle\sum_{r=1}^{k+1} r \times 2^{r - 1} = (k - 1)2^{k} + 1 + (k + 1)2^{k} = 2^{k}\big((k - 1) + (k + 1)\big) + 1 = 2k \times 2^{k} + 1\). ✓
  • \(= k \times 2^{k + 1} + 1\), the result for \(n = k + 1\). ✓
  • 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\). ✓
05
Analysis
[4 marks]

A sequence \(u_1, u_2, u_3, \dots\) is defined by \(u_1 = 3\) 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\).

  • When \(n = 1\): \(2^{1} + 1 = 3 = u_1\). True for \(n = 1\). ✓
  • Assume \(u_k = 2^{k} + 1\) for some positive integer \(k\). Target: \(u_{k+1} = 2^{k + 1} + 1\). ✓
  • By the recurrence, \(u_{k+1} = 2u_k - 1 = 2(2^{k} + 1) - 1 = 2^{k + 1} + 2 - 1 = 2^{k + 1} + 1\), the result for \(n = k + 1\). ✓
  • 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, \(u_n = 2^{n} + 1\) for all positive integers \(n\). ✓
06
Proof
[7 marks]

(a) Prove by induction that \(\displaystyle\sum_{r=1}^{n} \dfrac{r}{(r + 1)!} = 1 - \dfrac{1}{(n + 1)!}\) for all positive integers \(n\).

(b) Deduce that \(\displaystyle\sum_{r=1}^{n} \dfrac{r}{(r + 1)!} \lt 1\) for every positive integer \(n\).

  • (a) When \(n = 1\): LHS \(= \dfrac{1}{2!} = \dfrac{1}{2}\), RHS \(= 1 - \dfrac{1}{2!} = \dfrac{1}{2}\). True for \(n = 1\). ✓
  • Assume \(\displaystyle\sum_{r=1}^{k} \dfrac{r}{(r + 1)!} = 1 - \dfrac{1}{(k + 1)!}\). Target: \(1 - \dfrac{1}{(k + 2)!}\). The \((k + 1)\)th term is \(\dfrac{k + 1}{(k + 2)!}\). ✓
  • Since \((k + 2)! = (k + 2)(k + 1)!\), write \(\dfrac{1}{(k + 1)!} = \dfrac{k + 2}{(k + 2)!}\). ✓
  • \(\displaystyle\sum_{r=1}^{k+1} \dfrac{r}{(r + 1)!} = 1 - \dfrac{k + 2}{(k + 2)!} + \dfrac{k + 1}{(k + 2)!} = 1 - \dfrac{1}{(k + 2)!}\), the result for \(n = k + 1\). ✓
  • 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\). ✓
  • (b) \((n + 1)!\) is positive, so \(\dfrac{1}{(n + 1)!} \gt 0\) and the sum \(1 - \dfrac{1}{(n + 1)!}\) is less than \(1\) for every \(n\). ✓

Mark this once you have attempted all six and checked your working. It records a Practiced badge on the topic and adds a one-time bonus. Revealing the solutions alone does not count.