# Solving Second Order Recurrences

First consider a sequence, by which we mean a list of numbers which goes on forever.  An example is the well-known Fibonacci sequence
$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...$$
in which every number (except for the first two) is the sum of the previous two.  If we refer to these numbers, using function notation, as $a(0),a(1),a(2),a(3)$ and so on, the sequence is specified by the recurrence relation
$$a(n)=a(n-1)+a(n-2)\quad\hbox{for}\quad n\ge2 (1)$$ together with the initial conditions
$$a(0)\quad\hbox{and}\quad a(1)=1\ .$$
Equation $(1)$ is referred to as a second order recurrence because each number is determined by the previous two numbers.  If we wish, we can easily make up a third or higher order recurrence: for example, we might decide to write down a list in which each number is equal to the previous number, plus $14$ times the one before that, minus $24$ times the previous one again.  That is,
$$a(n)=a(n-1)+14a(n-2)-24a(n-3)\quad\hbox{for}\quad n\ge3\ .$$