Maths › Further Pure 2 › Recurrence relations
Recurrence relations
A sequence defined by its own previous terms can be solved outright: the same auxiliary equation that cracked differential equations works here, one step at a time instead of one instant at a time.
Builds on Second order equations and Proof by induction.
IN THIS TOPIC
- Solve first order recurrence relations with a complementary function and a particular solution.
- Handle second order relations via their auxiliary equation.
- Prove a closed form by induction and use recurrences to model growth.
WHAT YOU PROBABLY THINK
A sequence defined by a recurrence can only be evaluated term by term, never jumped into directly.
The same two-part solution
A recurrence such as un+1 = aun + f(n) splits exactly as a differential equation does. The complementary function solves the relation with the right-hand side removed, giving Aan. A particular solution handles f(n), guessed with the same shape as f. Adding them and fitting A to the first term gives a closed form, so any term can be reached directly and the opening claim is false.
WORKED EXAMPLE
A first order relation, solved
Solve un+1 = 5un + 8 with u₁ = 1.
Complementary function: A × 5n. For the constant 8, try a constant c: c = 5c + 8 gives c = −2.
So un = A × 5n − 2, and u₁ = 1 gives 5A − 2 = 1, so A = 3/5.
That is un = 3 × 5n-1 − 2. Checking: 1, 13, 73, 373 from the recurrence, and the same from the formula.
Second order, and proving it
For un+2 + bun+1 + cun = f(n), substitute un = mn into the homogeneous version and every term carries mn, leaving an auxiliary equation in m. Distinct roots give Am₁n + Bm₂n; a repeated root needs the extra factor of n. Two initial terms fix both constants.
WORKED EXAMPLE
A second order relation
Solve 2un+2 + 7un+1 − 15un = 6 with u₁ = 10 and u₂ = −17.
Auxiliary: 2m² + 7m − 15 = 0, so m = 3/2 or m = −5.
Particular solution, trying a constant k: 2k + 7k − 15k = −6k = 6, so k = −1.
un = A(3/2)n + B(−5)n − 1. The two conditions give 1.5A − 5B = 11 and 2.25A + 25B = −16, so A = 4 and B = −1.
Checking at n = 3: the formula gives 137.5, and the recurrence gives the same.
A closed form can also be proved by induction, which is what an exam usually asks when it supplies the answer: verify the first term, assume the formula at n = k, and substitute into the recurrence to reach n = k + 1.
YOUR TURN
Induction on a closed form
Given un+1 = 3un + 4 with u₁ = 1, prove by induction that un = 3n − 2.
Show the working
Base: u₁ = 3 − 2 = 1, as given.
Assume uk = 3k − 2. Then uk+1 = 3(3k − 2) + 4 = 3k+1 − 6 + 4 = 3k+1 − 2.
That is the formula at k + 1, so by induction it holds for all positive integers n. The terms 1, 7, 25, 79 confirm it.
THE EXAM BIT
- Name the complementary function and the particular solution separately; the marks are split between them.
- For a constant right-hand side try a constant; if that clashes with the complementary function, try a multiple of n.
- A second order relation needs two initial terms, so expect two simultaneous equations at the end.
- For an induction proof, substitute the assumed formula into the recurrence rather than working backwards from the target.
CHECK YOURSELF
Write down the auxiliary equation for un+2 − 5un+1 + 6un = 0, and its general solution.
Show a hint
Substitute u sub n equals m to the n.
Show the answer
m
²
−
5
m
+
6
=
0
,
s
o
m
=
2
o
r
3
.
T
h
e
g
e
n
e
r
a
l
s
o
l
u
t
i
o
n
i
s
u
{
{
_
{
n
}
}
}
=
A
×
2
{
{
^
{
n
}
}
}
+
B
×
3
{
{
^
{
n
}
}
}
.
Recurrences solve like differential equations: complementary function plus particular solution, constants fitted to the initial terms.
Second order relations use an auxiliary equation in m; a repeated root needs the extra factor of n.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- Solve first order recurrence relations with a complementary function and a particular solution.
- Handle second order relations via their auxiliary equation.
- Prove a closed form by induction and use recurrences to model growth.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.