A recurrence relation defines terms of a sequence using earlier terms.

For example,

$$a_n=a_{n-1}+3,\qquad a_0=2$$

defines the sequence

$$2,5,8,11,\ldots$$

The recurrence describes how to obtain the next value; the initial conditions determine which sequence is meant.

A recurrence may depend on several earlier terms. The Fibonacci sequence is defined by

$$F_n=F_{n-1}+F_{n-2},$$

with $F_0=0$ and $F_1=1$.

Recursive definitions

The same idea can define discrete objects rather than numbers: specify base objects and rules for constructing larger ones from smaller ones.

Recurrences are natural whenever a problem at size $n$ is built from smaller instances. They appear in algorithms, combinatorics, dynamical systems and numerical methods.