- #1
Pietjuh
- 76
- 0
For our combinatorics class there is a bonus excercise in which we have to solve the following recurrence relation:
[tex]L_k(x) = L_{k-1}(x) + xL_{k-2}(x)[/tex]
My first thought was to construct the following generating function:
[tex]F(x,y) = \sum_{k=0}^{\infty} L_k(x) y^k[/tex].
By putting in the recurrence relation I found a formula for this generating function:
[tex]F(x,y) = \frac{1+xy}{1-y-xy^2}[/tex]
Using the geometric series I found that this equals to:
[tex]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}[/tex]
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 [tex]L_k(x)[/tex], but I could'nt do it :(
Could someone give me a hint in which direction to look for now?
Thanks in advance!
[tex]L_k(x) = L_{k-1}(x) + xL_{k-2}(x)[/tex]
My first thought was to construct the following generating function:
[tex]F(x,y) = \sum_{k=0}^{\infty} L_k(x) y^k[/tex].
By putting in the recurrence relation I found a formula for this generating function:
[tex]F(x,y) = \frac{1+xy}{1-y-xy^2}[/tex]
Using the geometric series I found that this equals to:
[tex]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}[/tex]
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 [tex]L_k(x)[/tex], but I could'nt do it :(
Could someone give me a hint in which direction to look for now?
Thanks in advance!