Recurrence relations

A recurrence relation is an equation that defines each term of a sequence as a function of its preceding terms. For example, a sequence $(a_n)$ might be defined by $a_n = a_{n-1} + 3$ with $a_1 = 2$.

Important properties

• Initial conditions are needed to start the sequence.

• Recurrence relations can be linear or non-linear.

• Solving a recurrence relation means finding a formula for the $n$th term without needing to compute all previous terms.

• Many famous sequences, like the Fibonacci numbers, are defined by recurrence relations.