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.

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.