Find a closed formula for the generating function given the recursion equation.

Question

Suppose we have the recursion equation $b_{n+2}=5b_{n+1}-2b_n$. where $b_0=1, b_1 = 2$. I'm trying to find a closed formula for the generating function. I tried to find the characteristic equation and obtained $r^2-5r+2=0$. Then we could find $b_n = Ar_1^n+Br_2^n$ by solving $A$ and $B$ from $b_0$ and $b_1$. The final result is $$ b_n = \frac{\sqrt{17}-1}{2\sqrt{17}}\left(\frac{5+\sqrt{17}}{2}\right)^n+\frac{\sqrt{17}+1}{2\sqrt{17}}\left(\frac{5-\sqrt{17}}{2}\right)^n $$ I wonder is there a different approach to solve for the generating function using recursive equation?

Answer 1

Yes, of course. The generating function has the form$$f(r)=\frac{Ar+B}{r^2-5r+2}=\frac{C}{r-r_1}+\frac{D}{r-r_2},$$ but $A,B$ are not your constants. You can expand it by the geometric series and hopefully you get the same result.