Polynomial recurrence equation

[Pietjuh]

For our combinatorics class there is a bonus excercise in which we have to solve the following recurrence relation:

$$L_k(x) = L_{k-1}(x) + xL_{k-2}(x)$$

My first thought was to construct the following generating function:

$$F(x,y) = \sum_{k=0}^{\infty} L_k(x) y^k$$.

By putting in the recurrence relation I found a formula for this generating function:

$$F(x,y) = \frac{1+xy}{1-y-xy^2}$$

Using the geometric series I found that this equals to:

$$F(x,y) = (1+xy)\sum_{k=0}^{\infty} (y+xy^2)^k = \sum_{k=0}^{\infty} (1+xy)(xy^2)^k\frac{(1+xy)^k}{(xy)^k} = \sum_{k=0}^{\infty}\sum_{n=0}^k{k\choose n}(1+xy)x^ny^{n+k}$$

Now I've tried all afternoon to rewrite this whole powerseries in terms of y, so I can equate the generating function with this powerseries and find the required $$L_k(x)$$, but I could'nt do it :(

Could someone give me a hint in which direction to look for now?

Thanks in advance!

 

[Hurkyl]

Reverse the order of summation. (the idea is analogous to reversing the order of integration in an iterated integral)

 

[wais]

It seems like you are on the right track with using generating functions to solve this polynomial recurrence equation. One possible direction to look at is using the binomial theorem to expand the powers of (1+xy) in your generating function. This can help you rewrite the powerseries in terms of y and potentially lead to finding a closed form expression for L_k(x). Another approach could be to use the method of undetermined coefficients to find a particular solution for the recurrence relation, and then use the general solution to find L_k(x). I would also suggest consulting with your instructor or classmates for further guidance and clarification. Good luck!