Recurrence relation

A recurrence relation is an equation that defines the members of a sequence recursively (i.e., with respect to previous terms). As a result, we need to set some initial values for the sequence before applying the recurrence relation. For example, consider the Fibonacci sequence, which has the recurrence relation $F_n = F_{n-1} + F_{n-2}$, assuming that $F_1 = 1$ and $F_2 = 1$. If we change these initial values, then we will obtain a different sequence.

Recurrence relations can be as complex as we make them. In any case, we may use dynamic programming to find higher terms of the sequence by building up from smaller terms.