TITLE: Solve $h_{n} = h_{n-1} + h_{n-2}$ with the method of generating functions.
QUESTION [1 upvotes]: 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!

REPLY [1 votes]: 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}.$$
{"set_name": "stack_exchange", "score": 1, "question_id": 3434371}