D2PureCore

Recurrence Relations

A recurrence relation defines each term from the one before, rather than from its position. It is how sequences are often generated in real life — this month’s value depends on last month’s — and it introduces periodic and convergent behaviour.

24 min Video by TLMaths Sequences and Series

The big picture

There are two ways to describe a sequence. A position-to-term\textbf{position-to-term} rule (like un=3n+1u_n = 3n + 1) lets you jump straight to any term. A recurrence relation\textbf{recurrence relation} (or term-to-term rule) instead says how to get the next term from the current one, such as un+1=un+3u_{n+1} = u_n + 3. The recurrence view matches how change actually accumulates — savings that grow by a percentage each year, a drug clearing from the body each dose, a population changing each generation. Learning to generate terms, and to classify a sequence as increasing, decreasing, periodic or convergent, is what turns this from notation into a modelling tool.

A-Level Maths D2-02: Inductive Definitions and Recurrence RelationsCurated by Kepler, not produced by us. Watch it, then work through the notes below.
Open on YouTube

What you'll be able to do

  • Distinguish position-to-term from term-to-term (recurrence) definitions
  • Generate terms from a recurrence relation and a starting value
  • Recognise periodic, increasing, decreasing and convergent sequences
  • Interpret a recurrence in a modelling context
1

Two ways to define a sequence

A position-to-term\textbf{position-to-term} rule gives unu_n directly in terms of nn: put in the position, get the term. A recurrence relation\textbf{recurrence relation} gives un+1u_{n+1} in terms of unu_n: it tells you how to step from one term to the next, and needs a starting value to get going.

For example un+1=un+3u_{n+1} = u_n + 3 with u1=2u_1 = 2 generates 2,5,8,11,…2, 5, 8, 11, \ldots — the same sequence a position rule un=3n−1u_n = 3n - 1 describes, but built step by step.

un+1=f(un),u1=au_{n+1} = f(u_n), \quad u_1 = a
Each term from the previous one, plus a starting value.
Example 1A sequence has un+1=2un−1u_{n+1} = 2u_n - 1 with u1=3u_1 = 3. Find the first four terms.
1u1=3u_1 = 3.
2u2=2(3)−1=5u_2 = 2(3) - 1 = 5.
3u3=2(5)−1=9u_3 = 2(5) - 1 = 9.
4u4=2(9)−1=17u_4 = 2(9) - 1 = 17.
Answer
3,5,9,173, 5, 9, 17

Tip — Keep unu_n and un+1u_{n+1} straight: unu_n is the term you have, un+1u_{n+1} is the one you are computing. Muddling them is the main pitfall.

2

Describing long-term behaviour

Once a sequence is generated, you describe how it behaves. It may be increasing\textbf{increasing} (each term larger), decreasing\textbf{decreasing} (each smaller), periodic\textbf{periodic} (the terms cycle and repeat with a fixed period), or convergent\textbf{convergent} (the terms settle towards a limit).

A periodic sequence is worth spotting: un+1=1unu_{n+1} = \tfrac{1}{u_n} with u1=2u_1 = 2 gives 2,12,2,12,…2, \tfrac12, 2, \tfrac12, \ldots — period 2. In such cases you can find far-off terms by using the cycle rather than computing every step.

Why this works

A convergent\textbf{convergent} sequence approaches a limit\textbf{limit} LL where the term stops changing: L=f(L)L = f(L). Setting un+1=un=Lu_{n+1} = u_n = L and solving is exactly how you find the value an iterative process settles on — the seed of the Numerical Methods chapter.

3

Recurrences as models

Recurrence relations shine in modelling, because “next depends on now” is how most real processes work. A savings account with interest, a course of medication, or a fish population each naturally give a recurrence, and summing the terms answers questions like “total taken after 10 doses”.

Example 1A patient takes 10 mg of a drug daily. Each day 20% of the drug present is cleared before the next dose. Write a recurrence for the amount unu_n just after the nn-th dose.
1Just before the next dose, 80% remains: 0.8un0.8 u_n.
2Then a new 10 mg dose is added.
3So un+1=0.8un+10u_{n+1} = 0.8 u_n + 10, with u1=10u_1 = 10.
Answer
un+1=0.8un+10,  u1=10u_{n+1} = 0.8u_n + 10,\; u_1 = 10

Think like an examiner

  • Track the subscripts carefully: substitute the current term unu_n to produce un+1u_{n+1}, one step at a time.
  • For a periodic sequence, state the period and use the cycle to find distant terms rather than iterating dozens of times.
  • To find a limit of a convergent sequence, set un+1=un=Lu_{n+1} = u_n = L and solve the resulting equation.
  • In modelling questions, define your variable clearly (what unu_n represents and when it is measured) before writing the recurrence.

Common misconceptions

Confusing unu_n (the current term) with un+1u_{n+1} (the next).
Substitute the known unu_n into the rule to get un+1u_{n+1}; keep the indices distinct.
Trying to jump to the 50th term of a recurrence by a position formula that was not given.
Either iterate, or exploit periodicity/convergence — a recurrence does not always have a simple closed form.
Forgetting the starting value when generating terms.
A recurrence needs an initial term (u1u_1) to be defined.
Assuming every sequence converges.
Sequences can increase without bound, oscillate, or cycle; check the behaviour before claiming a limit.

Recurrence essentials

un+1=f(un)u_{n+1} = f(u_n)
Term-to-term rule.
u1=au_1 = a
Needs a starting value.
L=f(L)L = f(L)
Limit of a convergent sequence.

Stretch yourself

A sequence is defined by un+1=12un+3u_{n+1} = \tfrac{1}{2}u_n + 3 with u1=4u_1 = 4. Show that it converges, and find its limit.

Hint — Generate a few terms to see the trend, then set un+1=un=Lu_{n+1} = u_n = L and solve for the limit.

Reveal solution
SolutionTerms: u1=4u_1 = 4, u2=5u_2 = 5, u3=5.5u_3 = 5.5, u4=5.75u_4 = 5.75, … creeping towards a value. At the limit, un+1=un=Lu_{n+1} = u_n = L, so L=12L+3⇒12L=3⇒L=6L = \tfrac12 L + 3 \Rightarrow \tfrac12 L = 3 \Rightarrow L = 6. The sequence increases but is bounded above by 6, so it converges to 6. Setting L=f(L)L = f(L) to find the settling value is precisely the fixed-point idea used in numerical iteration. ■\blacksquare

Questions students ask

What is a recurrence relation?
A rule that gives each term of a sequence from the previous one, such as un+1=2un−1u_{n+1} = 2u_n - 1, together with a starting value. It defines the sequence step by step rather than by position.
How is it different from a position-to-term formula?
A position-to-term formula like un=3n+1u_n = 3n + 1 lets you compute any term directly from nn. A recurrence only tells you how to get the next term from the current one, so you generally build the sequence in order.
What is a periodic sequence?
One whose terms repeat in a fixed cycle, like 2,12,2,12,…2, \tfrac12, 2, \tfrac12, \ldots (period 2). You can find far-off terms by working out where they fall in the cycle instead of iterating every step.
How do I find the limit of a convergent sequence?
At the limit the terms stop changing, so set un+1=un=Lu_{n+1} = u_n = L and solve for LL. This gives the value the sequence approaches.

Key takeaways

  • A recurrence defines un+1u_{n+1} from unu_n and needs a starting value.
  • Position-to-term rules jump to any term; recurrences build the sequence in order.
  • Sequences may be increasing, decreasing, periodic or convergent.
  • A limit satisfies L=f(L)L = f(L) — the fixed-point idea.
  • Recurrences model real “next depends on now” processes.

How this fits the course

Related

Test yourself

Answer a few questions, then review anything you missed.

Prefer paper? Open the written self-check

Answer each question before opening its answer. This self-check does not record a quiz score.

  1. For un+1=un+4u_{n+1} = u_n + 4, u1=3u_1 = 3, the third term u3u_3 is:

    • 1111
    • 77
    • 1212
    • 1515
    Show answer and explanation

    Answer: 1111

    u2=7u_2 = 7, u3=11u_3 = 11.

  2. A recurrence relation defines each term from:

    • the previous term
    • its position nn
    • the sum of all terms
    • the common ratio
    Show answer and explanation

    Answer: the previous term

    It is a term-to-term rule.

  3. For un+1=3un−2u_{n+1} = 3u_n - 2, u1=2u_1 = 2, the value of u2u_2 is:

    • 44
    • 66
    • 11
    • 88
    Show answer and explanation

    Answer: 44

    3(2)−2=43(2) - 2 = 4.

  4. The sequence 5,15,5,15,…5, \tfrac15, 5, \tfrac15, \ldots is:

    • periodic (period 2)
    • convergent
    • increasing
    • arithmetic
    Show answer and explanation

    Answer: periodic (period 2)

    It cycles between two values every two terms.

  5. For a convergent sequence, the limit LL satisfies:

    • L=f(L)L = f(L)
    • L=0L = 0
    • L=u1L = u_1
    • L=f(u1)L = f(u_1)
    Show answer and explanation

    Answer: L=f(L)L = f(L)

    At the limit the term stops changing, so un+1=un=Lu_{n+1} = u_n = L.

  6. The limit of un+1=13un+4u_{n+1} = \tfrac13 u_n + 4 (convergent) is:

    • 66
    • 44
    • 1212
    • 33
    Show answer and explanation

    Answer: 66

    L=13L+4⇒23L=4⇒L=6L = \tfrac13 L + 4 \Rightarrow \tfrac23 L = 4 \Rightarrow L = 6.

Next step

Keep practising

Start with the quiz above to check the key ideas. You can also choose another topic from the practice library.

Browse practice topics

Related lessons

All 8 lessons

Put the methods into practice: see how A-Level maths duels work. An account is required to play; the overview and sample are public.