# How can I finish up my generating function for second degree recurrences?

I am trying to generalize the solution for recurrences of form $F_n = bF_{n-1} + aF_{n-2}$ using generating functions.

If $G(x) = \sum_{n=0}^{\infty} F_nx^n$ then I was able to eventually derive that:

$$G(x) = \frac{F_0 + x \cdot (F_1 - bF_0)}{1 - bx - ax^2}$$

However I don't know where to take it from here. Normally this is where you apply partial fraction decomposition and then start converting each piece back to a closed-form power of something, but I am a little stuck because I'm not sure what the correct way is to split this up.

Let $R$ and $r$ be the two roots of that quadratic. Then:

$$G(x) = \frac{F_0 + x \cdot (F_1 - bF_0)}{(x-r)(x-R)} = \frac{C_1}{x-r} + \frac{C_2}{x-R}$$

which implies

$$C_1 \cdot (x-R) + C_2 \cdot (x-r) = F_0 + x \cdot (F_1 - bF_0)$$

If I set $x = R$ then:

$$C_2 = \frac{F_0 + R \cdot (F_1 - bF_0)}{R-r}$$

If I set $x=r$ then:

$$C_1 = \frac{F_0 + r \cdot (F_1 - bF_0)}{r-R}$$

Meaning:

$$G(x) = \frac{F_0 + r \cdot (F_1 - bF_0)}{(r-R)(x-r)} + \frac{F_0 + R \cdot (F_1 - bF_0)}{(R-r)(x-R)}$$

I guess we could just convert all that stuff to constants, multiply by $-1/-1$, absorb the negatives into the constants, and say:

$$G(x) = c_0 \cdot \frac{1}{r-x} + c_1 \cdot \frac{1}{R-x}$$

Divide stuff out:

$$G(x) = c_0 \cdot \frac{1/r}{1-x/r} + c_1 \cdot \frac{1/R}{1-x/R}$$

Re-absorb into new constants:

$$G(x) = \alpha \cdot \frac{1}{1-(1/r)x} + \beta \cdot \frac{1}{1-(1/R)x}$$

Does this imply that:

$$[x^n]G(x) = F(n) = \alpha \cdot (1/r)^n + \beta \cdot (1/R)^n$$

This still seems off to me because normally I am dealing with the roots and not inverse roots in the closed form. I would have expected something that looks like $\alpha \cdot r^n + \beta \cdot R^n$

HINT Apply quadratic formula to factor the denominator (you will get a couple of cases depending on $a$ and $b$) and apply partial fractions to get (for fixed constant $C$ and roots of the denominator $r,R$): $$G(x) = \frac{Cx}{(x-r)(x-R)} = \frac{C_1}{x-r} + \frac{C_2}{x-R}$$ which is now a sum of geometric series, easily decomposable into pwoer series...

UPDATE

Continuing your partial fractions, you have $$x(C_1+C_2) - C_1R -C_2r = x(F_1-bF_0) + F_0 \quad \forall x$$ which yields $$F_0 = - C_1R -C_2r \\ F_1 = bF_0 + C_1 + C_2$$

Can you finish this?

• $r = \frac{b + \sqrt{b^2 + 4a}}{-2a}$ and $R = \frac{b - \sqrt{b^2 + 4a}}{-2a}$? – user438407 Apr 20 '17 at 15:09
• Also the numerator isn't fully multipliable (?) by $x$ – user438407 Apr 20 '17 at 15:11
• @user438407 this is standard partial fractions decomposition -- are you familiar with this technique? – gt6989b Apr 20 '17 at 15:13
• Yes but my results get uglier and uglier as I progress – user438407 Apr 20 '17 at 15:17
• I added more to my post to show my steps – user438407 Apr 20 '17 at 15:20