STEP sequences, series and induction: guide and practice problems

Sequences and series questions reward you for finding the pattern early and then proving it properly, usually by induction or telescoping.

Where it comes from: Sequences and series in A Level Pure; proof by induction and the method of differences in Further Pure.

Key ideas

Telescoping: write the term as a difference f(n) - f(n + 1) (or f(n - 1) - f(n + 1)), then most terms cancel.
Recurrences like u -> u^2 - 2 become easy with u = t + 1/t.
Differentiate a geometric series to sum r x^r and r^2 x^r.
To trap a sequence, sum a recurrence identity, then bound each term using what you have already proved.

Common traps

An induction step that uses the result for n + 1 instead of proving it.
Starting a sum at the wrong index after a shift.
Claiming a limit without showing the extra terms tend to zero.

Practice problems

Original problems in the style of STEP. Try each one for at least 20 minutes before you open a hint; write a full solution, then compare.

Problem 1: A squaring recurrence · STEP 2 style

The sequence \(u_n\) is defined by \(u_1=\tfrac52\) and \(u_{n+1}=u_n^2-2\).

Prove by induction that \(u_n=2^{2^{n-1}}+2^{-2^{n-1}}\).
Show that \(\displaystyle\prod_{k=1}^{n}u_k=\frac23\left(2^{2^n}-2^{-2^n}\right)\).
Find \(\displaystyle\lim_{n\to\infty}\frac{u_1u_2\cdots u_n}{u_{n+1}}\).

Hint 1

If \(u=t+t^{-1}\) then \(u^2-2=t^2+t^{-2}\).

Hint 2

Multiply the product by \(t-t^{-1}\) with \(t=2\): \((t-t^{-1})(t+t^{-1})=t^2-t^{-2}\), and so on.

Full solution

(i) \(u_1=2+\tfrac12=\tfrac52\). If \(u_n=t+t^{-1}\) with \(t=2^{2^{n-1}}\), then \(u_{n+1}=t^2+2+t^{-2}-2=t^2+t^{-2}\), and \(t^2=2^{2^n}\). So the formula holds for all \(n\).

(ii) Let \(t=2\). Then \((t-t^{-1})u_1u_2\cdots u_n=(t-t^{-1})(t+t^{-1})(t^2+t^{-2})\cdots(t^{2^{n-1}}+t^{-2^{n-1}})\). Each step doubles the exponent, giving \(t^{2^n}-t^{-2^n}\). Since \(t-t^{-1}=\tfrac32\), the product is \(\tfrac23\left(2^{2^n}-2^{-2^n}\right)\).

(iii) \(\dfrac{\prod u_k}{u_{n+1}}=\dfrac23\cdot\dfrac{2^{2^n}-2^{-2^n}}{2^{2^n}+2^{-2^n}}\to\dfrac23\).

Results: Limit \(\frac23\).

2 more sequences, series and induction problems

Sums with powers of two; Trapping a slowly growing sequence. Each with two hints and a full solution.

Included with A Level plans, and with IB, IGCSE or CBSE plans.

Next steps

Related topics: Complex numbers and polynomials · Integration. Stuck? Read the problem-solving strategies. Ready for the real thing? Official STEP past papers.

STEP is run by OCR. A Level Math Revision is independent: it is not affiliated with or endorsed by OCR, the University of Cambridge or any university. Every problem here is our own, written in the style of STEP; for real papers use OCR's official past papers.