home

# Recurrence relations

Sequences of numbers where the $$n$$-th term is defined by the prior term(s) are a recurrence relation.

An example of the is the Fibonacci sequence where $F_n = F_{n-1} + F_{n-2}$ and the initial terms $$F_0 = 0$$ and $$F_1 = 1$$.

To enable direct computation of some element $$a_n$$ sequence that can be modelled in the following forms may be equivalently expressed to remove the serial dependency.

\begin{align} a_n &= d \cdot a_{n-1} \\ a_0 &= k \\[8pt] a_n &= k \cdot d^n \end{align}

and

\begin{align} a_n - a_{n-1} &= k \\ a_0 &= c \\[8pt] a_n &= c + \sum_{i=1}^n k \end{align}