Maths › Further Pure 2 › Recurrence relations

Recurrence relations

Solve a linear recurrence by combining the complementary function, the general solution of the homogeneous relation, with a particular solution. Initial terms determine the constants. Long-term behaviour is set by the term whose root has the greatest modulus, provided its coefficient is non-zero; roots of equal modulus and truncated models need separate analysis.

Year FMEDEXCEL 9FM0 FP2 6.1, 6.2, 6.3; 9FM0 D2 6.1, 6.2

Builds on Second order equations and Proof by induction and Sequences and sigma notation.

IN THIS TOPIC

  • Solve first order recurrence relations with a complementary function and a particular solution.
  • Handle second order relations through their auxiliary equation, adding a particular solution when the relation has a right-hand side.
  • Multiply the trial solution by n when it duplicates a term of the complementary function.
  • Describe a sequence as monotonic, convergent, divergent, oscillating or periodic, naming the root that decides it and the condition that root has to meet.
  • Work with the Fibonacci and Lucas numbers, and use the algebraic properties of the golden ratio.
  • Set up a recurrence from a modelling context, integer part function included, 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.

A linear recurrence solves as a differential equation does: a complementary function from the auxiliary equation, a particular solution matching the right-hand side, and the constants fitted to the initial terms. The closed form then gives any term directly, so un+1 = 5un + 8 with u₁ = 1 becomes un = 3 × 5n-1 − 2.

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 taken with the same functional form as f. Add them and fit A to the first term; the result is a closed form that gives any term directly, without computing the terms before it.

Four amber dots in a row carrying the values one, thirteen, seventy-three and three hundred and seventy-three, joined by coral arrows each labelled multiply by five and add eight. Underneath, the closed form is evaluated at each position and gives the same four numbers.
FIG. 1The recurrence starting at 1, each term five times the last plus eight: the terms computed one at a time, and the closed form agreeing with each of them.

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.

A particular solution may duplicate a term of the complementary function. If the right-hand side is constant and 1 is a root of the auxiliary equation, a constant trial substitutes to zero, so use a multiple of n instead. The same applies when f(n) is a power already present in the complementary function: multiply the trial by a sufficient power of n.

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.

Naming the behaviour

A closed form describes a sequence as well as computing it, and five words name the possible descriptions. A sequence is monotonic if it moves the same way at every step, increasing throughout or decreasing throughout. It is convergent if its terms settle towards a single value and divergent if they do not. It oscillates if it swings either side of a value rather than approaching from one side, and it is periodic if a block of terms repeats.

Those descriptions are independent of one another. Take un+1 = −0.5un + 9 from u₀ = 10. It runs 10, 4, 7, 5.5, 6.25 with closed form 4(−0.5)n + 6, so it both oscillates and converges to 6. Take un+1 = −un from 3 and it runs 3, −3, 3, −3, bounded between −3 and 3 and divergent all the same, since staying inside a range is a weaker thing than settling on a value. Four closed forms drawn side by side separate the words for good.

Four sequences and the words for them: monotonic convergent, oscillating convergent, bounded but divergent, and monotonic divergent
Describe the drawing

Four small stem plots of eight terms each. The first, four times a half to the n plus six, drops towards a dashed line at six and never turns back, so it is monotonic and convergent. The second, with minus a half in place of the half, lands either side of the same dashed six by shrinking amounts, so it converges while oscillating. The third, three times minus one to the n, jumps between the dashed bounds at three and minus three forever: bounded, but settling nowhere, so it diverges. The fourth, three times five to the n minus one, less two, grows so fast that its fifth term runs off the top of the panel and its eighth is two hundred and thirty-four thousand three hundred and seventy-three.

FIG. 2Four sequences plotted term by term: 4(0.5)ⁿ + 6 falling to 6, 4(−0.5)ⁿ + 6 crossing 6 at every step and still reaching it, 3(−1)ⁿ bounded between −3 and 3 without settling, and 3 × 5ⁿ⁻¹ − 2 climbing off the top of its panel.

Read all of this off the roots. A factor mn tends to zero when |m| < 1, alternates in sign when m < 0, and grows in magnitude when |m| > 1. Among terms whose coefficients are non-zero, a unique root of largest modulus usually controls the long-term behaviour. So 3 × 5n−1 − 2 from the first worked example is monotonic and divergent, while A(3/2)n + B(−5)n − 1 from the second is divergent and oscillating for A and B non-zero, its swings widening because the negative root is the larger in modulus.

Two cases need separate analysis. If the constant multiplying the largest-modulus root is zero, that root contributes nothing and the next root governs the behaviour: with B = 0 above, the sequence is A(3/2)n − 1, which diverges without oscillating, so the description changes although the auxiliary equation has not. If two roots have equal modulus, as with a pair ±2, neither dominates and the two terms must be combined before the sequence can be described.

The Fibonacci numbers and the golden ratio

One second order relation turns up more often than the rest. The Fibonacci numbers obey Fn+2 = Fn+1 + Fn with F₁ = F₂ = 1, so they run 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 and onwards. Taking F₀ = 0, which the relation forces from F₂ = F₁ + F₀, makes the constants easier to fit. A Fibonacci-like sequence obeys the same relation from different starting terms, and the Lucas numbers, with L₁ = 1 and L₂ = 3, are the standard one.

The method of the section above solves it. Substituting un = mn gives the auxiliary equation m² = m + 1, that is m² − m − 1 = 0, whose roots are (1 + √5)/2 and (1 − √5)/2. The first is the golden ratio φ, which is 1.6180 to four decimal places; write ψ for the second, which is −0.6180.

The properties φ is known for are algebra rather than decimals, and the auxiliary equation supplies them. From m² = m + 1 comes φ² = φ + 1, and dividing by φ gives φ = 1 + 1/φ, so 1/φ = φ − 1 = 0.6180 and φ stands one above its own reciprocal. The sum and product of the roots give φ + ψ = 1 and φψ = −1, so ψ is both 1 − φ and −1/φ.

Since |ψ| is below 1 its powers tend to zero, so the reading from the section above applies: Fn grows like φn, and the ratio of a term to the one before it approaches φ. The ratios 89/55 = 1.6182 and 144/89 = 1.6180 show that happening.

WORKED EXAMPLE

The Fibonacci closed form

Solve Fn+2 = Fn+1 + Fn with F₀ = 0 and F₁ = 1, and use the result to find F₂₀.

The auxiliary equation m² − m − 1 = 0 has the distinct roots φ and ψ, so Fn = Aφn + Bψn.

F₀ = 0 gives A + B = 0, so B = −A. Then F₁ = 1 gives A(φ − ψ) = 1, and φ − ψ = √5, so A = 1/√5.

That is Fn = (φn − ψn)/√5, worth recognising on sight when a question hands it to you.

At n = 20 the ψ term has shrunk to nothing that matters: φ²⁰/√5 = 6765.00003, so F₂₀ = 6765, which the recurrence confirms. The size of ψn/√5 stays below a half, so Fn is the nearest whole number to φn/√5 throughout.

GUIDED PRACTICE

The Lucas numbers

The Lucas numbers satisfy the same recurrence with L₁ = 1 and L₂ = 3. Write down the next four terms, and find a closed form.

Show the working

The relation gives 4, 7, 11, 18, and running it backwards gives L₀ = L₂ − L₁ = 2.

The auxiliary equation has not changed, so Ln = Aφn + Bψn. Now L₀ = 2 gives A + B = 2 and L₁ = 1 gives Aφ + Bψ = 1, which A = B = 1 satisfies since φ + ψ = 1.

So Ln = φn + ψn, tidier than the Fibonacci form. Checking at n = 5: 11.0902 − 0.0902 = 11, which is L₅.

From the second term onwards Ln is the nearest whole number to φn, since ψn is under a half in size: φ⁵ = 11.0902 gives 11 and φ¹⁰ = 122.9919 gives 123.

Building the relation from the situation

A modelling question begins with a definition rather than with algebra. Say what un stands for and what n counts, then write the one sentence that turns a single step of the situation into arithmetic. Three standard contexts are a savings account paying interest and topped up each year, a population growing by a fixed percentage while a fixed number is harvested, and 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.

Some discrete models have to round, because animals and coins come in whole units. The integer part function INT(x) throws the fractional part away, and a model that truncates builds it into the relation: a herd growing by 8% a year with ten sold at each year end is un+1 = INT(1.08un) − 10. From u₀ = 400 the terms run 400, 422, 445, 470, 497, since 1.08 × 422 = 455.76 truncates to 455 before the ten come off. The truncation sits inside the relation, so the relation is not linear and the complementary function method does not apply. A recurrence containing INT is normally iterated unless an explicit form is established.

The same herd without the truncation obeys un+1 = 1.08un − 10, with closed form 275 × 1.08n + 125. After eight years the untruncated model gives 634 animals where the truncated one gives 629. Each step discards less than one animal, and the discards compound, so the untruncated version reads high and the gap widens. State which model the question specifies.

The figure plots the two together and shows where they separate.

The truncated herd against the smooth model 275 × 1.08ⁿ + 125: identical for two years, then parting by five animals at eight
Describe the drawing

A rising curve for the model two hundred and seventy-five times one point nought eight to the n plus one hundred and twenty-five, with the truncated herd drawn on it as nine dots. The dots sit exactly on the curve at nought and one years and then fall a little below it, ending at six hundred and twenty-nine against the curve's six hundred and thirty-four. The panel alongside plots the difference between the two year by year: nothing for two years, then a bar that grows steadily to five animals, because each year's discarded fraction is carried forward and compounds.

FIG. 3The truncated herd plotted against the smooth model 275 × 1.08ⁿ + 125: the two agree at 0 and 1 years, and the gap between them widens year by year to 629 against 634 at eight.

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 closed form has to be read back into the situation. The 2n term dominates, so the ratio of successive populations tends to 2, while the alternating term (−1)n/3 stays bounded and neither grows nor tends to zero. Say so in words, and name the modelling assumption you would question first.

Proving the closed form

When a question supplies the closed form it is asking for an induction proof rather than 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. Starting from the n = k + 1 statement and working back to the assumption assumes what is to be proved.

On the left, three stages of an induction stacked downwards: the base case, the assumption at k, and the conclusion at k plus one, joined by coral arrows. On the right, the same three stages carried out on real numbers, each line ending in a power of three minus two.
FIG. 4Proving a closed form by induction: the base case starts the chain and the recurrence carries the formula from each term to the next.

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, so the relation has a stated meaning.
  • Name the complementary function and the particular solution separately, and show each before adding 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.
  • Describe the behaviour and give the reason: which root, its modulus, and whether it is negative. Say so explicitly when two roots share the largest modulus, or when a constant multiplying a root is zero.
  • A recurrence containing INT is normally iterated unless an explicit form is established. Truncate before the next step rather than after.
  • In a Fibonacci question quote the surd roots and the identity that the golden ratio squares to one more than itself; give an exact value unless the question requests a decimal approximation.

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; the Fibonacci relation gives m squared = m + 1, whose positive root is the golden ratio.

Modelled situations that grow by a factor and change by a fixed amount each step give u sub n+1 = au sub n + b.

A factor mⁿ tends to zero when |m| < 1, alternates in sign when m < 0, and grows in magnitude when |m| > 1; among terms with non-zero coefficients a unique largest modulus usually decides the long-term behaviour, while equal dominant moduli, cancellation and truncation need separate analysis, and bounded is not the same as convergent.

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.

Question workbook

PDF · 77 KB · print edition · white background

Question workbook

PDF · 78 KB · screen edition · navy

Answer book

PDF · 97 KB · fully worked · navy
15 questions on this topicAnswer them one at a time and mark yourself against the worked answer.Practise this topic

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, adding a particular solution when the relation has a right-hand side.
  • Multiply the trial solution by n when it duplicates a term of the complementary function.
  • Describe a sequence as monotonic, convergent, divergent, oscillating or periodic, naming the root that decides it and the condition that root has to meet.
  • Work with the Fibonacci and Lucas numbers, and use the algebraic properties of the golden ratio.
  • Set up a recurrence from a modelling context, integer part function included, 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.