How to solve recurrence relations using generating functions?

Question

I'm trying to solve recurrences like:

an=5an−1−6an−2,a0=1,a1=2

I can solve this using the characteristic equation method, but I want to learn the generating functions approach.

Define G(x)=∑n=0∞anxn. Then:

∑n=2∞anxn=5∑n=2∞an−1xn−6∑n=2∞an−2xn

How do I manipulate these sums to get a closed form for G(x), and then extract an explicit formula for an?

0 Answers