Recurrence Relation — Definition, Formula & Examples

A recurrence relation is a rule that defines each term in a sequence based on one or more of the terms that came before it. For example, saying "each term is twice the previous term" is a recurrence relation.

A recurrence relation is an equation of the form $a_n = f(a_{n-1}, a_{n-2}, \ldots, a_{n-k})$ that, together with a set of initial conditions $a_0, a_1, \ldots, a_{k-1}$ , uniquely determines every term of a sequence for $n \geq k$ .

Key Formula

a_n = f(a_{n-1}, a_{n-2}, \ldots, a_{n-k})

Where:

$a_n$ = The nth term of the sequence
$f$ = A function relating the current term to previous terms
$k$ = The number of previous terms the relation depends on (the order)

How It Works

To use a recurrence relation, you need two things: the recursive rule and enough initial values (called initial conditions) to get started. You then apply the rule repeatedly to generate successive terms. For instance, the Fibonacci sequence is defined by

a_n = a_{n-1} + a_{n-2}

with

a_1 = 1

and

a_2 = 1

. Without initial conditions, a recurrence relation does not specify a unique sequence. In many problems, you can also "solve" a recurrence relation by finding a closed-form formula that gives

a_n

directly in terms of

n

Worked Example

Problem: A sequence is defined by

a_1 = 3

and

a_n = 2a_{n-1} + 1

for

n \geq 2

. Find

a_4

Find a₂: Substitute n = 2 into the recurrence relation.

a_2 = 2a_1 + 1 = 2(3) + 1 = 7

Find a₃: Substitute n = 3.

a_3 = 2a_2 + 1 = 2(7) + 1 = 15

Find a₄: Substitute n = 4.

a_4 = 2a_3 + 1 = 2(15) + 1 = 31

Answer:

a_4 = 31

Why It Matters

Recurrence relations model real situations where each stage depends on previous stages, such as population growth, compound interest, and algorithm running times. They appear throughout discrete mathematics, computer science, and precalculus courses whenever sequences are defined iteratively rather than by an explicit formula.

Common Mistakes

Mistake: Writing a recurrence relation without specifying initial conditions.

Correction: A recurrence relation alone can describe infinitely many sequences. You must state the starting value(s) — for example,

a_1 = 3

— to pin down a unique sequence.