0
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.