01 Key Concepts
Definition
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).
Initial 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.
Linear 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).
Solving by Iteration
Compute term by term directly from the initial conditions, useful for finding specific values even without a closed-form formula.
Closed-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.
02 Solved Examples
Example 1 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(3) = a(2)+a(1) = 1+1 = 2.
- a(4) = a(3)+a(2) = 2+1 = 3.
- a(5) = a(4)+a(3) = 3+2 = 5.
- a(6) = a(5)+a(4) = 5+3.
Answer: a(6) = 8
Example 2 A sequence is defined by a(n) = 2*a(n-1), with a(1) = 3. Find a(4).
- a(2) = 2*a(1) = 2*3 = 6.
- a(3) = 2*a(2) = 2*6 = 12.
- a(4) = 2*a(3) = 2*12.
Answer: a(4) = 24
Example 3 A sequence is defined by a(n) = a(n-1) + 5, with a(1) = 2. Find a closed-form formula for a(n).
- Each term adds 5 to the previous one, starting from a(1)=2.
- After (n-1) steps of adding 5: a(n) = 2 + 5*(n-1).
Answer: a(n) = 2 + 5(n-1), which simplifies to a(n) = 5n - 3
03 Practice Questions
1A sequence has a(n) = a(n-1) + 3, a(1) = 1. Find a(4).
10 (1,4,7,10)
2A sequence has a(n) = 3*a(n-1), a(1) = 2. Find a(3).
18 (2,6,18)
3For Fibonacci with a(1)=1, a(2)=1, find a(7).
13
4What are 'initial conditions' in a recurrence relation?
The starting value(s) needed to begin generating the sequence
5What is a 'closed-form solution'?
An explicit formula for a(n) that doesn't require computing previous terms
📄 Recurrence Relations — Downloadable Worksheet
10 questions with a full answer key. Grab the PDF to print, or try the interactive version in your browser.