Recurrence relations

A recurrence relation defines each term of a sequence from the ones before it, like the Fibonacci sequence. Many can be solved to give a formula for the nth term directly.

Key facts

  • uₙ₊₁ = f(uₙ) with a starting value u₀ or u₁.
  • First order linear: uₙ₊₁ = auₙ + b has solution uₙ = Aaⁿ + b/(1 − a) (a ≠ 1).
  • Fixed point (limit) L solves L = f(L).
  • Fibonacci: Fₙ₊₁ = Fₙ + Fₙ₋₁.

Worked examples

Example 1

uₙ₊₁ = 2uₙ + 3, u₀ = 1. Find u₃ and a formula for uₙ.

  1. u₁ = 5, u₂ = 13, u₃ = 29.
  2. uₙ = A × 2ⁿ − 3; u₀ = 1 gives A = 4.
  3. uₙ = 4 × 2ⁿ − 3. Check: 4 × 8 − 3 = 29.

Answer: u₃ = 29, uₙ = 4 × 2ⁿ − 3