Thread: 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!

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.