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 through their auxiliary equation.
- Set up a recurrence from a modelling context and interpret the closed form back in that context.
- Fit the constants to the given initial terms.
- Prove a supplied closed form by induction.
COMMON MISCONCEPTION
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) and is guessed with the same shape as f. Add them, fit A to the first term, and you have a closed form that reaches any term directly, with no term-by-term climb.
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, so c = 5c + 8 and 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. The recurrence gives 1, 13, 73, 373 and so does the formula.
Second order relations
For un+2 + bun+1 + cun = f(n), substitute un = mn into the homogeneous version. Every term carries a factor of mn, and what survives is an auxiliary equation in m. Distinct roots give Am₁n + Bm₂n, a repeated root needs the extra factor of n, and two initial terms fix both constants.
Watch for a particular solution that clashes with the complementary function. If the right-hand side is a constant and 1 happens to be a root of the auxiliary equation, a constant trial fails and you need a multiple of n instead. The same warning applies when f(n) is a power that already appears in the complementary function.
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.
Check at n = 3. The formula gives 137.5, and so does the recurrence.
Building the relation from the situation
Modelling questions give away marks before any algebra starts, because the setting-up carries its own. Say what un stands for and what n counts, then write the one sentence that turns a single step of the situation into arithmetic. A savings account paying interest and topped up each year, a population growing by a fixed percentage while a fixed number is harvested, a loan gathering interest with a repayment taken off. All three land on un+1 = aun + b, and the work above then solves them.
WORKED EXAMPLE
A savings account, modelled and solved
£2000 is deposited. Each year the balance grows by 4% and a further £500 is paid in at the year end. Model the balance and find it after 10 years.
Let un be the balance in pounds after n years. Then u₀ = 2000 and un+1 = 1.04un + 500.
Complementary function A × 1.04n. Trying a constant c for the 500 gives c = 1.04c + 500, so c = −12500.
un = A × 1.04n − 12500, and u₀ = 2000 gives A = 14500.
So un = 14500 × 1.04n − 12500, and after ten years the balance is £8963.54. Running the recurrence ten times by hand gives the same figure.
Second order relations model situations in which a term leans on the two before it. Take a colony whose pairs breed only from their second year, so that each year's population is the survivors plus two offspring for every pair alive two years ago, giving pn+2 = pn+1 + 2pn. The auxiliary equation m² − m − 2 = 0 has roots 2 and −1, so pn = A × 2n + B(−1)n.
Starting from p₀ = p₁ = 1 the constants come out as A = 2/3 and B = 1/3, and the formula reproduces 1, 1, 3, 5, 11, 21 exactly. Then interpret it, because the interpretation mark is separate. The 2n term takes over, so the colony settles into doubling each year, while the alternating term is a small wobble that neither grows nor dies. Say so in words, and say which modelling assumption you would question first.
Proving the closed form
When a question supplies the answer it usually wants an induction proof, not a derivation. Verify the first term, assume the formula at n = k, then substitute that assumption into the recurrence and simplify until the formula at n = k + 1 appears. Working backwards from the target loses marks even when the algebra is right.
GUIDED PRACTICE
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 every positive integer n. The terms 1, 7, 25, 79 confirm it.
ASSESSMENT FOCUS
- Define u sub n and n in words before writing a modelled recurrence. That sentence is a mark.
- Name the complementary function and the particular solution separately, since the marks are split between them.
- For a constant right-hand side try a constant, and 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.
- Substitute the assumed formula into the recurrence in an induction proof; never work backwards from the target.
- Check your closed form against the first three or four terms before writing it as the answer.
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² − 5m + 6 = 0, so m = 2 or 3. The general solution is un = A × 2n + B × 3n.
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, and a repeated root needs the extra factor of n.
Modelled situations that grow by a factor and change by a fixed amount each step give u sub n+1 = au sub n + b.
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.
Or read them with their worked answers on the recurrence relations questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Solve first order recurrence relations with a complementary function and a particular solution.
- Handle second order relations through their auxiliary equation.
- Set up a recurrence from a modelling context and interpret the closed form back in that context.
- Fit the constants to the given initial terms.
- Prove a supplied closed form by induction.
Open the full revision checklist to see every objective in the course in one place.