What is a recurrence relation?
A sequence is a list of numbers in order: u₀, u₁, u₂ … A recurrence relation (also called a recursive formula) says how to get the next term from earlier terms.
Example: u(n+1) = u(n) + 3, u(0) = 2. So u₁ = 5, u₂ = 8, u₃ = 11.
You need two things: the rule and the starting value(s). Same rule, different start = different sequence.
Recursive vs explicit formula
A recursive formula needs the term before. An explicit (direct) formula gives any term straight from n. For u(n+1) = u(n) + 3, u(0) = 2, the explicit formula is u(n) = 2 + 3n. To find u(100), the explicit formula is much faster.
Arithmetic and geometric recurrences
Add a fixed number d: u(n+1) = u(n) + d → arithmetic, u(n) = u(0) + n·d.
Multiply by a fixed number r: u(n+1) = r·u(n) → geometric, u(n) = u(0)·rⁿ.
If r > 1 the terms grow; if 0 < r < 1 they shrink towards 0; if r is negative the signs flip each time.
First-order linear recurrences: u(n+1) = a·u(n) + b
This rule mixes multiply and add. It models savings with deposits, medicine in the blood, or fish in a lake. Such a step-by-step model is called a discrete dynamical system.
Fixed point (equilibrium)
A fixed point L does not change: L = a·L + b, so L = b ÷ (1 − a) (when a ≠ 1).
- If −1 < a < 1, the terms move towards L (stable).
- If a > 1 or a < −1, they run away from L (unstable).
- If a is negative, they jump above and below L (oscillate).
Explicit formula
u(n) = L + (u(0) − L)·aⁿ. The gap from L is multiplied by a every step.
Web (cobweb) diagram
Plot y = a·x + b and y = x. Start at u(0), go up to the line, across to y = x, and repeat. The path stairs or spirals into the crossing point, which is the fixed point.
Second-order recurrences and Fibonacci
A second-order rule uses two earlier terms, so it needs two starting values. Fibonacci: F(n+2) = F(n+1) + F(n), F(0) = F(1) = 1 → 1, 1, 2, 3, 5, 8, 13 …
The ratio of neighbours gets closer to the golden ratio ≈ 1.618. A sum can also be defined recursively: S(n) = S(n−1) + u(n).
Key formulas and definitions
- u(n+1) = u(n) + d → u(n) = u(0) + n·d
- u(n+1) = r·u(n) → u(n) = u(0)·rⁿ
- u(n+1) = a·u(n) + b, fixed point L = b ÷ (1 − a)
- u(n) = L + (u(0) − L)·aⁿ
- F(n+2) = F(n+1) + F(n)
Worked examples
1. u(n+1) = u(n) + 4, u(0) = 3. Find u₁ to u₄.
u₁ = 7, u₂ = 11, u₃ = 15, u₄ = 19.
2. u(n+1) = 3·u(n), u(0) = 2. Find u₄ and the explicit formula.
u₁ = 6, u₂ = 18, u₃ = 54, u₄ = 162. Explicit: u(n) = 2·3ⁿ; check 2·81 = 162.
3. Write a recursive formula for 50, 45, 40, 35 …
Each term is 5 less: u(n+1) = u(n) − 5, u(0) = 50.
4. u(n+1) = 0.5·u(n) + 10, u(0) = 2. Find u₁, u₂, u₃ and the fixed point.
u₁ = 11, u₂ = 15.5, u₃ = 17.75. L = 10 ÷ (1 − 0.5) = 20. The terms approach 20.
5. A pond has 1,000 fish. Each year 20% die and 150 are added. Write the rule and find the long-run number.
u(n+1) = 0.8·u(n) + 150, u(0) = 1000. L = 150 ÷ 0.2 = 750 fish. u₁ = 950, u₂ = 910 … falling towards 750.
6. For u(n+1) = 0.8·u(n) + 150, u(0) = 1000, find u(10) with the explicit formula.
u(n) = 750 + (1000 − 750)·0.8ⁿ = 750 + 250·0.8ⁿ. 0.8¹⁰ ≈ 0.107, so u(10) ≈ 750 + 26.8 ≈ 777 fish.
7. Fibonacci starting 1, 1. Find F(9) (the 10th term).
1, 1, 2, 3, 5, 8, 13, 21, 34, 55. F(9) = 55.
Common mistakes
- Forgetting the starting value: a rule alone does not fix the sequence.
- Mixing up u(n) and u(n+1): the right side uses the term you already know.
- Using L = b ÷ (1 − a) when a = 1: then there is no fixed point (the sequence is arithmetic).
- Thinking every sequence with a fixed point reaches it: if |a| > 1 it runs away.