Mathwords logoMathwords

Recurrence Equation — Definition, Formula & Examples

A recurrence equation (also called a recurrence relation) is a rule that defines each term in a sequence based on one or more of its preceding terms. Combined with an initial value, it completely determines every term in the sequence.

A recurrence equation is an equation of the form an=f(an−1,an−2,…,an−k)a_n = f(a_{n-1}, a_{n-2}, \ldots, a_{n-k}) for n≥kn \geq k, where ff is a given function and a0,a1,…,ak−1a_0, a_1, \ldots, a_{k-1} are specified initial conditions. The positive integer kk is called the order of the recurrence.

Key Formula

an=f(an−1,an−2,…,an−k)a_n = f(a_{n-1}, a_{n-2}, \ldots, a_{n-k})
Where:
  • ana_n = The nth term of the sequence
  • ff = A function relating the current term to previous terms
  • kk = The order of the recurrence (how many previous terms are used)

How It Works

To use a recurrence equation, start with the given initial value(s) and repeatedly apply the rule to generate successive terms. For example, if a1=3a_1 = 3 and an=2an−1+1a_n = 2a_{n-1} + 1, you plug in n=2n = 2 to get a2a_2, then n=3n = 3 to get a3a_3, and so on. A first-order recurrence depends on just the immediately preceding term, while a second-order recurrence (like the Fibonacci sequence) depends on the two preceding terms. Many recurrence equations can also be solved for a closed-form expression that gives ana_n directly in terms of nn.

Worked Example

Problem: Given the recurrence equation an=3an−1−2a_n = 3a_{n-1} - 2 with initial condition a1=5a_1 = 5, find a2a_2, a3a_3, and a4a_4.
Find a₂: Substitute n = 2 into the recurrence.
a2=3a1−2=3(5)−2=13a_2 = 3a_1 - 2 = 3(5) - 2 = 13
Find a₃: Substitute n = 3, using the value of a₂.
a3=3a2−2=3(13)−2=37a_3 = 3a_2 - 2 = 3(13) - 2 = 37
Find a₄: Substitute n = 4, using the value of a₃.
a4=3a3−2=3(37)−2=109a_4 = 3a_3 - 2 = 3(37) - 2 = 109
Answer: The first four terms are 5, 13, 37, 109.

Why It Matters

Recurrence equations appear throughout discrete mathematics, computer science (analyzing algorithm run-times), and financial modeling (compound interest and loan amortization). In precalculus and calculus courses, recognizing that arithmetic and geometric sequences are special cases of recurrence relations helps unify your understanding of sequences and series.

Common Mistakes

Mistake: Forgetting to state or use the initial condition(s).
Correction: A recurrence equation alone does not determine a unique sequence. You must always specify initial values like a1=5a_1 = 5; without them, infinitely many sequences satisfy the same recurrence.