Solve $h_{n} = h_{n-1} + h_{n-2}$ with the method of generating functions.

Question

I have to solve the above recurrence relation with initial conditions $h_0 = 1$ and $h_1 = 3$. I find the generating function for the relation to be $g(x) = \frac{1+2x}{1-x-x^2}$ but then I am unsure how to go on and find the closed form for $h_n$ from this. The denominator has irrational roots and I am unsure how to go about dealing with this because I would typically just use partial fractions to find expressions that are easily translatable to power series but I don't know how to do that in this case. Thanks for any help!

Answer 1

Hint:

$$\frac a{z-r}+\frac b{z-s}=\frac{(a+b)z-(as+br)}{(z-r)(z-s)}$$

is the generating function of

$$ar^{-n-1}+bs^{-n-1}.$$

Answer 2

Let $g(x)=\sum_{n=0}^\infty h_nx^n$ be your generating function. We have that $$\sum_{n=0}^\infty h_nx^n=1+2x+\sum_{n=1}^\infty h_{n-1}x^n+ \sum_{n=2}^\infty h_{n-2}x^n,$$ so that $$g(x)=1+2x+xg(x)+x^2g(x).$$ From here, we can immediately deduce $$g(x)=\frac{1+2x}{1-x-x^2}.$$