Solving Recurrence Relations With Ordinary Generating Functions

Technique

The basic technique is to multiply the equation with $z^{N}$ , sum over all $N$ , recast in terms of the generating function (or derivative, etc). Then solve for the generating function, and expand to get the coefficient of $z^{N}$ . That will be your solution.

One very important caveat is that one must account for the initial conditions! You cannot solve for it in the end - they are part of your equation from the start!

Example

$\begin{equation*} a_{n}=5a_{n-1}-8a_{n-2}+4a_{n-3},a_{0}=0,a_{1}=1,a_{2}=4 \end{equation*}$

becomes:

$\begin{equation*} a_{n}=5a_{n-1}-8a_{n-2}+4a_{n-3}+\delta_{n,1}-\delta_{n,2} \end{equation*}$

How did I get these? Assume that if the index is negative, the value is 0. Then plug in $n=1$ and figure out what term to add to make the equation valid for $a_{1}$ , and so on.

Now multiply by $z^{n}$ and sum:

$\begin{equation*} A(z)=5zA(z)-8z^{2}A(z)+4z^{3}A(z)+z-z^{2} \end{equation*}$

Solve for $A(z)$ , decompose into partial fractions, and get the solution.

Notes

When you have constant coefficient linear equation, if your root is complex, there will be some kind of periodicity!
If a root is -1, you’ll get some periodicity.