BitWithBite
Discrete Mathematics · Quick Reference
Recurrence Relations Cheat Sheet
In one line: a recurrence relation defines each term of a sequence in terms of previous terms — a natural way to describe patterns that build on themselves, like the famous Fibonacci sequence.
Key Ideas
1Definition. An equation that expresses a term a(n) in a sequence using one or more previous terms, such as a(n-1) or a(n-2).
2Initial Conditions. The starting value(s) needed to fully define a sequence, since the recurrence alone only describes how to get from one term to the next.
3Linear Recurrence Relations. Relations where each term is a linear combination of previous terms, such as a(n) = a(n-1) + a(n-2) (the Fibonacci relation).
4Solving by Iteration. Compute term by term directly from the initial conditions, useful for finding specific values even without a closed-form formula.
5Closed-Form Solutions. An explicit formula for a(n) in terms of n alone, without needing to know previous terms — often much faster to compute for large n.
Worked Examples
The Fibonacci sequence is defined by a(n) = a(n-1) + a(n-2), with a(1)=1, a(2)=1. Find a(6).
a(6) = 8
A sequence is defined by a(n) = 2*a(n-1), with a(1) = 3. Find a(4).
a(4) = 24
A sequence is defined by a(n) = a(n-1) + 5, with a(1) = 2. Find a closed-form formula for a(n).
a(n) = 2 + 5(n-1), which simplifies to a(n) = 5n - 3
Practice Yourself
A sequence has a(n) = a(n-1) + 3, a(1) = 1. Find a(4).
10 (1,4,7,10)
A sequence has a(n) = 3*a(n-1), a(1) = 2. Find a(3).
18 (2,6,18)
For Fibonacci with a(1)=1, a(2)=1, find a(7).
13
What are 'initial conditions' in a recurrence relation?
The starting value(s) needed to begin generating the sequence