# Recurrence relation

A recurrence relation is a formula which defines a sequence of numbers by telling you how to get to the next term of the sequence from previous ones.

For instance, the Fibonacci numbers $F(n)$ are defined by the recurrence relation $\begin{gather*} F(n) = F(n-1) + F(n-2)\\ F(1)=F(2)=1, \end{gather*}$

which says that each number in the sequence is equal to the sum of the two previous ones, and also gives the starting values.

Similarly, the sequence of powers of $2$ can be defined by $\begin{gather*} a_{n+1} = 2a_n\\ a_0=1. \end{gather*}$

Sometimes we can find ways to turn a recurrence relation into an ordinary formula which gives the $n$th term in terms of $n$, but this is not always easy. For the powers of $2$ example, $a_n=2^n$, but a formula for the $n$th Fibonacci number is harder to obtain.