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} \]


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