Recurrence Relation Explained with Worked Examples

A recurrence relation defines each term from the previous one: , together with a starting value.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Recurrence relation means

Instead of a formula for the th term, a recurrence relation tells you how to get from one term to the next. For example, with gives 3, 7, 15, 31, …

Arithmetic sequences have and geometric sequences have .

Some sequences settle towards a limit, which satisfies . The standard examples are the arithmetic sequence, the geometric sequence and Fibonacci-type sequences, and a repeating pattern is in periodic and oscillating sequences.

This page is part of Sequences in Algebra. Topics that work alongside it: Arithmetic sequence: nth term, Geometric sequence, Fibonacci-type sequences, Quadratic sequence nth term, Linear nth term in the form dn + k and Periodic and oscillating sequences.

What is it used for?

A recurrence relation defines each term of a sequence from the one before it. You need the rule and a starting value.

How to use recurrence relation

  1. Write the starting value.
  2. Substitute it into the rule to get the next term.
  3. Repeat as many times as needed.
  4. To find a limit, solve .

Graph

u(n+1) = 0.5·u(n) + 2, starting at u(1) = 100123456789024681012u(n+1) = 0.5·u(n) + 2, starting at u(1) = 10nu(n)Graph with x from 0 to 9 and y from 0 to 12. Shows u(n) (8); the curve y = 4+0*x.

The terms settle towards 4, the value where u = 0.5u + 2 gives the same number back.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: generate terms

A sequence has and . Find .

Worked example
Answer
u4=31u_{4}=31
  1. Find u₂
  2. Find u₃
  3. Find u₄

Example 2: find a limit

A sequence has . Find the limit.

Worked example
Answer
L=8L=8
  1. Set the limit equal to itself
  2. Solve

Example 3: doubling and subtracting

A sequence has and . Find .

Worked example
Answer
4141
  1. Find u₂
  2. Find u₃
  3. Find u₄

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

uₙ₊₁ = 2uₙ + 1, u₁ = 1

u₂ = 3, u₃ = 7, u₄ = 15

u₄ = 15.

uₙ₊₁ = 0.5uₙ + 3

limit L = 0.5L + 3

L = 6.

uₙ₊₁ = uₙ + 4, u₁ = 3

u₅ = 3 + 16

19.

uₙ₊₁ = 3uₙ, u₁ = 2

u₄ = 2 × 27

54.

Word problems

A recurrence uₙ₊₁ = f(uₙ) with a starting value generates the sequence term by term. If it converges, the limit L satisfies L = f(L).

Iterate

uₙ₊₁ = 2uₙ + 1, u₁ = 1. Find u₄.

  1. u₂ = 3
  2. u₃ = 7
  3. u₄ = 15
  4. Check: ✓15

Limit

uₙ₊₁ = 0.5uₙ + 3. Solve L = 0.5L + 3.

  1. 0.5L = 3
  2. Check: ✓6

Arithmetic type Higher

uₙ₊₁ = uₙ + 4, u₁ = 3. Find u₅.

  1. 3 + 4 × 4
  2. Check: ✓19

Geometric type Higher

uₙ₊₁ = 3uₙ, u₁ = 2. Find u₄.

  1. 2 × 27
  2. Check: ✓54

Common mistakes

Skipping terms

u₃ from u₁ ✗

go one step at a time ✓

Each term needs the previous.

Limit when |ratio| ≥ 1

exists ✗

diverges ✓

Check the coefficient.

Index slip

u₁ = first term ✗

be careful with u₀ ✓

Starting index.

L = f(L) misused

set uₙ = 0 ✗

set L = f(L) ✓

Fixed point.

Exam tips

  1. Start value matters.
  2. One step at a time.
  3. Limit: L = f(L).
  4. Converges if |coefficient| < 1.
  5. Write the terms.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. u₃ for uₙ₊₁ = 2uₙ, u₁ = 5 Foundation

20

2. u₄ for uₙ₊₁ = uₙ + 3, u₁ = 1 Foundation

10

3. Limit of uₙ₊₁ = 0.4uₙ + 6 Foundation

10

4. u₃ for uₙ₊₁ = uₙ² − 1, u₁ = 2 Higher

8

5. Limit of uₙ₊₁ = 0.5uₙ + 1 Higher

2

6. u₅ for uₙ₊₁ = 2uₙ + 1, u₁ = 0 Higher

15

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Recurrence relation
uₙ₊₁ = f(uₙ).
Initial value
u₁.
Fixed point
L = f(L).
Convergent
Has a limit.
Divergent
No limit.
Iteration
Repeating the rule.

Frequently asked questions

What is a recurrence relation?

A rule giving each term from the previous one.

How do I find the limit?

Solve L = f(L).

When does it converge?

When the multiplier has modulus below 1.

What do I need to start?

An initial term.

Which page covers periodic sequences?

periodic and oscillating sequences.

Which page covers Fibonacci-type sequences?

Fibonacci-type sequences.

More in Algebra and the formula sheets.