Recurrence Relations

A recurrence relation defines each term of a sequence using the previous term(s). Instead of giving an explicit formula for u(n) in terms of n, we give a rule connecting u(n+1) to u(n), along with a starting value. This is an important topic in the Edexcel A-Level (9MA0) specification.

Key Definitions

Term	Meaning
Recurrence relation	A formula that gives u(n+1) in terms of u(n) (and possibly n)
Initial condition	The starting value, e.g. u(1) = 3, needed to generate the sequence
Increasing sequence	u(n+1) > u(n) for all n
Decreasing sequence	u(n+1) < u(n) for all n
Periodic sequence	A sequence that repeats with a fixed period: u(n+k) = u(n) for all n

Defining Sequences with Recurrence Relations

A recurrence relation has two parts:

The recursive rule, e.g. u(n+1) = 3u(n) - 1
The initial condition, e.g. u(1) = 2

Both are needed to uniquely define a sequence.

Worked Example 1

A sequence is defined by u(n+1) = 2u(n) + 3, u(1) = 1. Find the first five terms.

u(1) = 1
u(2) = 2(1) + 3 = 5
u(3) = 2(5) + 3 = 13
u(4) = 2(13) + 3 = 29
u(5) = 2(29) + 3 = 61

First five terms: 1, 5, 13, 29, 61

Worked Example 2

A sequence is defined by u(n+1) = u(n)² - 2, u(1) = 3. Find u(4).

u(1) = 3
u(2) = 9 - 2 = 7
u(3) = 49 - 2 = 47
u(4) = 2209 - 2 = 2207

Linking to Arithmetic and Geometric Sequences

Sequence type	Recurrence relation
Arithmetic (common difference d)	u(n+1) = u(n) + d
Geometric (common ratio r)	u(n+1) = r x u(n)

Worked Example 3

Write a recurrence relation for the sequence 5, 8, 11, 14, ...

This is arithmetic with d = 3. The recurrence relation is:

u(n+1) = u(n) + 3, u(1) = 5

Worked Example 4

Write a recurrence relation for the sequence 3, 6, 12, 24, ...

This is geometric with r = 2. The recurrence relation is:

u(n+1) = 2u(n), u(1) = 3

Increasing, Decreasing and Periodic Sequences

Increasing Sequences

A sequence is increasing if u(n+1) > u(n) for all n >= 1.

Example: u(n+1) = u(n) + 5, u(1) = 2 gives 2, 7, 12, 17, ... (always increasing since we add 5)

Decreasing Sequences

A sequence is decreasing if u(n+1) < u(n) for all n >= 1.

Example: u(n+1) = 0.5 x u(n), u(1) = 64 gives 64, 32, 16, 8, 4, ... (always decreasing)

Periodic Sequences

A sequence is periodic with period k if u(n+k) = u(n) for all n.

Worked Example 5

A sequence is defined by u(n+1) = 1/u(n), u(1) = 3. Show it is periodic and state the period.

u(1) = 3
u(2) = 1/3
u(3) = 1/(1/3) = 3
u(4) = 1/3
u(5) = 3

The sequence repeats: 3, 1/3, 3, 1/3, ...

The sequence is periodic with period 2.

Worked Example 6

A sequence is defined by u(n+1) = 6 - u(n), u(1) = 1. Find the first six terms and describe the behaviour.

u(1) = 1
u(2) = 6 - 1 = 5
u(3) = 6 - 5 = 1
u(4) = 6 - 1 = 5
u(5) = 6 - 5 = 1
u(6) = 6 - 1 = 5

The sequence is periodic with period 2: 1, 5, 1, 5, ...

Finding a Limit of a Convergent Sequence

If a sequence defined by a recurrence relation converges to a limit L, then as n tends to infinity, both u(n) and u(n+1) approach L. We can substitute L into the recurrence relation.

Worked Example 7

The sequence u(n+1) = (u(n) + 4) / 3, u(1) = 10, converges to a limit L. Find L.

At the limit: L = (L + 4) / 3

3L = L + 4

2L = 4

L = 2

Check: the sequence is 10, 14/3, 26/9, ... and does indeed approach 2.

Worked Example 8

A sequence is defined by u(n+1) = sqrt(5u(n) + 6), u(1) = 2. Find the limit to which the sequence converges.

At the limit: L = sqrt(5L + 6)

L² = 5L + 6

L² - 5L - 6 = 0

(L - 6)(L + 1) = 0

L = 6 or L = -1

Since all terms are positive (we start at 2 and take square roots), L = 6.

Exam Tips

Tip	Detail
Always state u(1)	A recurrence relation without an initial condition does not define a unique sequence
Show enough terms	To identify periodic behaviour, compute at least one full cycle
Convergence	To find a limit, set u(n+1) = u(n) = L and solve — but check the sequence actually converges
Calculator use	Use the ANS button to iterate quickly on your calculator
Subscript notation	Edexcel may use u(n+1) or various subscript forms; be comfortable with all

Practice Problems

A sequence is defined by u(n+1) = 3u(n) - 4, u(1) = 3. Find u(5). [Answer: 167]
A sequence is defined by u(n+1) = (u(n))² - 1, u(1) = 2. Find u(3). [Answer: 8]
Show that the sequence u(n+1) = -u(n) + 6, u(1) = 2 is periodic and state its period. [Answer: period 2, terms: 2, 4, 2, 4, ...]
The sequence u(n+1) = (2u(n) + 10) / 4 converges to L. Find L. [Answer: L = 5]
A sequence is defined by u(n+1) = sqrt(3u(n) + 10), u(1) = 1. Find the limit. [Answer: L = 5]

Summary

A recurrence relation defines u(n+1) in terms of u(n), with an initial condition.
Arithmetic sequences: u(n+1) = u(n) + d; geometric: u(n+1) = r x u(n).
Sequences can be increasing, decreasing, or periodic.
A periodic sequence of period k satisfies u(n+k) = u(n) for all n.
If a sequence converges to limit L, set u(n+1) = u(n) = L and solve.

A-Level Deep Dive: Recurrence Relations

Spec mapping

Edexcel 9MA0 specification, Section 4 — Sequences and series, sub-strand on recurrence covers work with sequences including those given by a formula for the nth term and those generated by a simple relation of the form $u_{n+1} = f(u_n)$ ; understand the meaning of and work with increasing sequences, decreasing sequences and periodic sequences (refer to the official specification document for exact wording). Recurrence relations sit at the centre of A-Level pure mathematics: they are explicitly tested on Paper 1, but appear synoptically across the specification. Section 9 (Numerical methods) is the most direct synoptic neighbour — fixed-point iteration $x_{n+1} = g(x_n)$ is the applied face of recurrence. Section 1 (Proof) uses recurrence as a primary domain for proof by induction. Section 8 (Differentiation) and Section 7 (Integration) connect through differential equations, the continuous analogue of recurrence. The Edexcel formula booklet does not list closed-form solutions for linear recurrences — these must be derived.

Worked example with full mark scheme

Question (8 marks):

The sequence $u_n$ is defined by $u_{n+1} = \tfrac{1}{2}u_n + 3$ with $u_1 = 0$ .

(a) Find $u_2$ , $u_3$ and $u_4$ . (2)

(b) Show, by induction or otherwise, that $u_n = 6 - 6 \cdot (\tfrac{1}{2})^{n-1}$ . (4)

Solution with mark scheme:

(a) Step 1 — iterate.

$u_2 = \tfrac{1}{2}(0) + 3 = 3$ . $u_3 = \tfrac{1}{2}(3) + 3 = \tfrac{9}{2}$ . $u_4 = \tfrac{1}{2}(\tfrac{9}{2}) + 3 = \tfrac{21}{4}$ .

B1 — at least two correct values. B1 — all three values correct, exact form preserved.

(b) Step 1 — base case.

For $n = 1$ : $u_1 = 6 - 6 \cdot (\tfrac{1}{2})^{0} = 6 - 6 = 0$ . This matches the given initial condition.

B1 — base case verified, with explicit substitution shown.

Step 2 — inductive step. Assume $u_k = 6 - 6 \cdot (\tfrac{1}{2})^{k-1}$ for some $k \geq 1$ . Show $u_{k+1} = 6 - 6 \cdot (\tfrac{1}{2})^{k}$ .

$u_{k+1} = \tfrac{1}{2}u_k + 3 = \tfrac{1}{2}\left(6 - 6 \cdot (\tfrac{1}{2})^{k-1}\right) + 3$

M1 — applies the recurrence to the inductive hypothesis correctly.

Step 3 — simplify.

$= 3 - 3 \cdot (\tfrac{1}{2})^{k-1} + 3 = 6 - 3 \cdot (\tfrac{1}{2})^{k-1} = 6 - 6 \cdot (\tfrac{1}{2})^{k}$

using $3 \cdot (\tfrac{1}{2})^{k-1} = 6 \cdot (\tfrac{1}{2})^{k}$ since $\tfrac{1}{2} \cdot 6 = 3$ .

A1 — algebra correct, target form reached.

Step 4 — conclude. "Since the result holds for $n = 1$ and the truth for $n = k$ implies the truth for $n = k+1$ , by mathematical induction $u_n = 6 - 6 \cdot (\tfrac{1}{2})^{n-1}$ for all $n \geq 1$ ."

A1 — explicit induction conclusion. Skipping this sentence costs the final A1 even when the algebra is right; examiners reward the formal closure.

(c) Step 1 — take the limit. As $n \to \infty$ , $(\tfrac{1}{2})^{n-1} \to 0$ since $|\tfrac{1}{2}| < 1$ , so $u_n \to 6$ .

M1 — recognises that $|r| < 1$ implies $r^{n} \to 0$ .

Step 2 — verify via fixed point. Setting $L = \tfrac{1}{2}L + 3$ gives $\tfrac{1}{2}L = 3$ , so $L = 6$ , confirming the limit independently.

A1 — limit $L = 6$ stated, and either method (closed form or fixed-point equation) properly justified.

Total: 8 marks (B3 M2 A3, split as shown).

Specimen question modelled on the Edexcel 9MA0 Paper 1 format

Question (6 marks): A sequence is defined by $u_{n+1} = \sqrt{2u_n + 3}$ with $u_1 = 1$ .

(a) Find $u_2$ and $u_3$ in exact form. (2)

(b) Given that the sequence converges to a limit $L$ , find the exact value of $L$ . (2)

Mark scheme decomposition by AO:

(a)

B1 (AO1.1a) — $u_2 = \sqrt{2(1) + 3} = \sqrt{5}$ .
B1 (AO1.1b) — $u_3 = \sqrt{2\sqrt{5} + 3}$ (exact surd form preserved; decimal approximations only earn this mark if accompanied by the exact expression).

(b)

M1 (AO2.1) — sets $L = \sqrt{2L + 3}$ , then squares to obtain $L^2 = 2L + 3$ , i.e. $L^2 - 2L - 3 = 0$ .
A1 (AO1.1b) — factorises $(L - 3)(L + 1) = 0$ , giving $L = 3$ (rejecting $L = -1$ since $L \geq 0$ as a square root).

(c)

M1 (AO2.4) — observes $u_1 = 1 < u_2 = \sqrt{5} \approx 2.236 < u_3 \approx 2.736 < L = 3$ , suggesting an increasing sequence bounded above by 3.
A1 (AO2.5) — concludes "the sequence is monotonically increasing and converges to 3 from below," with the reasoning that since $u_1 < L$ and the function $f(x) = \sqrt{2x + 3}$ satisfies $f(x) > x$ for $0 \leq x < 3$ , each iterate increases.

Total: 6 marks split AO1 = 3, AO2 = 3. Recurrence questions on 9MA0 are AO2-rich because they reward reasoning about behaviour — convergence, monotonicity, periodicity — rather than pure procedure.

Synoptic links

Connects to:

Section 9 — Numerical methods (fixed-point iteration): the iterative scheme $x_{n+1} = g(x_n)$ for solving $x = g(x)$ is literally a recurrence relation. The fixed point of the recurrence is the root of the equation. Convergence diagnostics (cobweb diagrams, the contraction condition) are inherited directly from recurrence theory.
Section 1 — Proof by induction: the natural setting for induction is "prove a property holds for every term of a recursively defined sequence." Closed-form formulae for recurrences are routinely established by induction in Paper 1 questions.
Section 4 — Arithmetic and geometric sequences: these are special cases of linear recurrences. Arithmetic: $u_{n+1} = u_n + d$ (constant additive step). Geometric: $u_{n+1} = r u_n$ (constant multiplicative step). Both are exactly solvable in closed form, and the general linear case $u_{n+1} = \alpha u_n + \beta$ blends them.
Section 7/8 — Differential equations: a differential equation $\tfrac{dy}{dx} = f(y, x)$ is the continuous analogue of a recurrence $u_{n+1} = f(u_n, n)$ . Euler's method, the simplest numerical solver, converts a differential equation back into a recurrence $y_{n+1} = y_n + h \cdot f(y_n, x_n)$ .
Cobweb and staircase diagrams: the geometric visualisation of recurrence behaviour. Plot $y = f(x)$ and $y = x$ ; iterate by alternately moving vertically to the curve and horizontally to the line. Convergent sequences spiral or staircase into the fixed point; divergent sequences fly off; periodic sequences trace closed cycles.

Mark-scheme literacy

Recurrence questions on 9MA0 split AO marks more evenly between AO1 and AO2 than most pure-mathematics topics:

AO	Typical share	Earned by
AO1 (knowledge / procedure)	40–55%	Iterating the recurrence, substituting values, computing terms in exact form
AO2 (reasoning / interpretation)	35–50%	Stating the fixed point as $L = f(L)$ , identifying periodicity, justifying monotonicity, concluding induction proofs
AO3 (problem-solving)	5–15%	Reverse-engineering closed forms, modelling discrete dynamics, recognising hidden recurrences

Examiner-rewarded phrasing: "stating the fixed point as $L = f(L)$ "; "since $u_n \to L$ as $n \to \infty$ , both sides of the recurrence tend to the same limit"; "the sequence is periodic with period 3 because $u_{n+3} = u_n$ for all $n$ "; "by mathematical induction, the result holds for all $n \in \mathbb{N}$ ." Phrases that lose marks: "the sequence settles down to" (vague — examiners want "converges to"); "loops back" instead of "is periodic"; ending an induction proof without the formal closing sentence; computing the fixed point but failing to check whether the sequence actually converges to it ( $L$ being a fixed point does not guarantee convergence — examiners increasingly probe this distinction at A*).

A specific Edexcel pattern to watch: questions that say "given that the sequence converges to $L$ " grant you convergence, and only ask you to find $L$ — a one-step $L = f(L)$ calculation. Questions that ask "show that the sequence converges" require additional reasoning about monotonicity and boundedness. Confusing the two costs marks in both directions.

Grade-band model answers

3-mark question

Question: A sequence is defined by $u_{n+1} = 5 - \tfrac{1}{2}u_n$ with $u_1 = 2$ . Given that the sequence converges to a limit $L$ , find the value of $L$ .

Grade C response (~210 words):

If the sequence converges to $L$ , then both $u_n$ and $u_{n+1}$ tend to $L$ , so substituting into the recurrence:

$L = 5 - \tfrac{1}{2}L$ .

Add $\tfrac{1}{2}L$ to both sides: $\tfrac{3}{2}L = 5$ , so $L = \tfrac{10}{3}$ .

Recurrence Relations

Recurrence Relations

Key Definitions

Defining Sequences with Recurrence Relations

Worked Example 1

Worked Example 2

Linking to Arithmetic and Geometric Sequences

Worked Example 3

Worked Example 4

Increasing, Decreasing and Periodic Sequences

Increasing Sequences

Decreasing Sequences

Periodic Sequences

Worked Example 5

Worked Example 6

Finding a Limit of a Convergent Sequence

Worked Example 7

Worked Example 8

Exam Tips

Practice Problems

Summary

A-Level Deep Dive: Recurrence Relations

Spec mapping

Worked example with full mark scheme

Specimen question modelled on the Edexcel 9MA0 Paper 1 format

Synoptic links

Mark-scheme literacy

Grade-band model answers

3-mark question

More in Mathematics