Glossary

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.