Originally Posted by

**galactus** Anyway, here's an example of a recurrence using GF

$\displaystyle a_{n}=5a_{n-1}-6a_{n-2}, \;\ a_{0}=1, \;\ a_{1}=0$

$\displaystyle A(x)=\sum_{n=0}^{\infty}a_{n}x^{n}$

$\displaystyle A(x)=1+5xA(x)-5x-6x^{2}A(x)$

Let y=A(x):

$\displaystyle y=1+5xy-5x-6x^{2}y$

$\displaystyle y=\frac{1-5x}{6x^{2}-5x+1}=\frac{-2}{1-3x}+\frac{3}{1-2x}$

Notice the familiar geometric series solution in the PFD, $\displaystyle \sum_{n=1}^{\infty}a_{n}=\frac{1}{1-x}$

This gives us $\displaystyle \boxed{a_{n}=3\cdot{2^{n}}-2\cdot{3^{n}}}$