1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Polynomial recurrence equation

  1. Dec 29, 2004 #1
    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!!
  2. jcsd
  3. Dec 29, 2004 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Reverse the order of summation. (the idea is analogous to reversing the order of integration in an iterated integral)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Polynomial recurrence equation
  1. Linear Recurrence (Replies: 2)

  2. Taylor Polynomial (Replies: 2)

  3. Polynomial division (Replies: 2)