Generating Function of Fibonacci sequence

Question

We have:

$$ F_n = \begin{cases} 1, & n = 0 \\ 1, & n= 1 \\F_{n-1}+F_{n-2}, & n \ge 2\end{cases} $$

Using generating function, I found $G(n) = \frac{1}{1-n-n^2}$ so far so good.

But now I'm blocked trying to figure out how to solve $\frac{C_1}{1-\alpha n}+\frac{C_2}{1-\beta n}$

I have

$C_1 + C_2 = 1$ and $ -(C_1\beta +C_2\alpha) = 0$

How should I proceed?

Answer 1

I believe you want to have $G(n)=\dfrac{C_1}{1-\alpha n}+\dfrac{C_2}{1-\beta n}$ right? That's a partial fraction decomposition. If you didn't study that, well with common denominator you get

$$G(n)=\dfrac{C_1(1-\beta n)+C_2(1-\alpha n)}{(1-\alpha n)(1-\beta n)}=\dfrac{1}{1-n-n^2}.$$

So you'll find your $\alpha$ and $\beta$ by factorising the polynomial $1-X-X^2$. Then you can solve your system with unknown $C_1$ and $C_2$ as you know $\alpha$ and $\beta$.