# Using generating functions with recursion?

• Oct 27th 2012, 02:52 PM
haytham12121
Using generating functions with recursion?
Let a0 = 0, a1 = 2, and a2 = 5. Use generating functions to solve the recurrence
equation an+3 = 5an+2 −7an+1 +3an +2n for n ≥ 0.

I first got:
f(x) = a0 + a1x + a2x^2 +.... + anx^n + ...
-5xf(x) = 0 - 5a0x - 5a1x^2 - ... - 5a(n-1)x^n
7x^2f(x) = ... + 7an-2^n - ...
-3x^3 f(x) = ... - 3an-3x^n - ...

i got it down to 1-5x+7x^2 - 3x^3 = (2x-4x^2 + 8x^3)/1-2x

Please help me out, I have to do a couple of these and If i understand one of them, I will understand all of them.
Thanks!
• Oct 27th 2012, 09:09 PM
chiro
Re: Using generating functions with recursion?
Hey haytham12121.

If your equation involving the x's is correct, then you will need to find the roots for the equation which will look like a quartic.

There is a complicated formula to solve quartics, but you can use something known as the rational root theorem to check for rational roots as well as the option of using a computer to calculate the roots straight away.

To get the polynomial, multiply both sides by (1-2x), collect terms and simplify to get a polynomial P(x) where P(x) = 0 and consider the above to get those roots.