What is a Recurrence Relation?
What you'll learn: You'll discover how recurrence relations define sequences by expressing each term using previous terms rather than an explicit formula.
The Core Idea
A recurrence relation is an equation that defines a sequence by describing how to compute each term from one or more earlier terms in the sequence. Instead of giving you a direct formula like "the nth term equals 2n + 3," a recurrence relation says something like "the nth term equals the sum of the two previous terms."
Think of it like a recipe that tells you how to make today's batch of cookies using yesterday's leftover ingredients—you need the history to create what comes next.
Anatomy of a Recurrence Relation
A recurrence relation has two essential parts:
- The recursive formula: How to compute term(s) from previous term(s)
- Initial conditions: The first term(s) that get the sequence started
Without initial conditions, you can't actually compute the sequence—it's like having instructions without a starting point.
The Fibonacci Example
The most famous recurrence relation is the Fibonacci sequence:
- Recurrence: F(n) = F(n-1) + F(n-2) for n ≥ 2
- Initial conditions: F(0) = 0, F(1) = 1
This generates: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Each term is the sum of the two preceding terms.
Other Examples
- Arithmetic progression: a(n) = a(n-1) + d (constant difference)
- Geometric progression: a(n) = r · a(n-1) (constant ratio)
- Factorial: n! = n · (n-1)! with 0! = 1
Recurrence relations appear naturally in counting problems, algorithm analysis, probability, and modeling processes that depend on previous states.
Key Takeaway: A recurrence relation defines a sequence recursively by expressing each term as a function of earlier terms, combined with initial conditions that anchor the sequence.