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{aligned} a_{n} & = d \cdot a_{n - 1} \\ a_{0} & = k \\ a_{n} & = k \cdot d^{n} \end{aligned}$

and

$\begin{aligned} a_{n} - a_{n - 1} & = k \\ a_{0} & = c \\ a_{n} & = c + \sum_{i = 1}^{n} k \end{aligned}$