# Polynomial recurrence equation

1. Dec 29, 2004

### 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?

2. Dec 29, 2004

### Hurkyl

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