Problem Solving

Recurrence Relation

Students build a new tower from pieces of two earlier towers.

Recurrence Relation definition

A recurrence relation connects terms of a sequence to terms at other indices, usually earlier ones.

In Spanish
relación de recurrencia
Topic
Algorithms and problem-solving

Recurrence Relation in a picture

Recurrence Relation diagramThe recurrence aₙ = aₙ₋₁ + 3 and a₀ = 2 produce 2, 5, 8, 11, and so on.Starting value: a₀ = 2Use this to begin the sequenceaₙ = aₙ₋₁ + 3Add 3 to get the next terma₁ = 5, a₂ = 8, a₃ = 11Apply the relation repeatedly
The recurrence aₙ = aₙ₋₁ + 3 and a₀ = 2 produce 2, 5, 8, 11, and so on.

How it works

For example, aₙ = aₙ₋₁ + 3 says each term is three more than the preceding term. Starting values determine which sequence satisfies the relation. A relation that depends on two previous terms generally needs two starting values. A recurrence can also model algorithm cost. In T(n) = T(n/2) + 1, the one extra unit represents the work before solving a half-size subproblem.

Worked examples

Find a₂ if a₀ = 4 and aₙ = 2aₙ₋₁.

a₁ = 8 and a₂ = 16.

Does aₙ = aₙ₋₁ + 1 specify a unique sequence by itself?

No. Different starting values give different sequences.

If T(1) = 1 and T(n) = T(n/2) + 1 for powers of two, find T(8).

T(2) = 2, T(4) = 3, and T(8) = 4. The recurrence counts one unit per halving plus the base case.

Common mistake

State the starting index and values. The recurrence tells how terms relate, and the starting data determine the result.

Quick check

What can you use to fix a one-step recurrence?

Can a recurrence use two earlier terms?

Show answer

Yes.

Does a recurrence always give a closed formula in n?

Show answer

No. It gives a relation, which may or may not be solved in closed form.

Sources

Flashcard

Recurrence Relation

Reveal the definition

A recurrence relation connects terms of a sequence to terms at other indices, usually earlier ones.

Effortless Math. “Recurrence Relation.” Math Dictionary.