Results 1 to 3 of 3

Math Help - Recursions and generating functions

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    12

    Recursions and generating functions

    Hi guys,

    Could you please walk me through this example, as I am struggling with this topic?



    Many thanks in advance.

    Banana1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2009
    Posts
    95
    http://www.math.upenn.edu/~wilf/gfologyLinked2.pdf

    excellent intro to generating functions, as well as advanced discussion.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Recursion and Generating Functions

    Hello Banana1
    Quote Originally Posted by Banana1 View Post
    Hi guys,

    Could you please walk me through this example, as I am struggling with this topic?



    Many thanks in advance.

    Banana1
    Starting with L(x) =\sum_{n=0}^{\infty} l_nx^n, write this using the first two terms that we've been given as:

    L(x) =2+x+\sum_{n=2}^{\infty}l_nx^n

    Then plug in the recurrence relation:

    L(x) =2+x+\sum_{n=2}^{\infty}(l_{n-1}+l_{n-2})x^n

    Next, separate the summations, taking out powers of x so that the power that's left matches the subscript of the l_n term:

    L(x) =2+x+x\sum_{n=2}^{\infty}l_{n-1}x^{n-1}+x^2\sum_{n=2}^{\infty}l_{n-2}x^{n-2}

    Next, we change the summation limits so that we get terms in x^n:

    L(x) =2+x+x\sum_{n=1}^{\infty}l_{n}x^{n}+x^2\sum_{n=0}^  {\infty}l_{n}x^{n}

    Now we can express the summations in terms of the original one for L(x):

    L(x) =2+x+x(L(x)-2)+x^2L(x) (That's the clever bit!)

    \Rightarrow L(x)(1-x-x^2)= 2-x

    \Rightarrow L(x) = \frac{2-x}{1-x-x^2}

    Then we get the Partial Fractions by equating the denominators:

    1-x-x^2 = (1-ax)(1-bx)

    Compare coefficients:

    \Rightarrow ab = -1, a+b = 1

    So a and b are the roots of m^2-m-1=0

    Let's say a = \frac{1+\sqrt5}{2}, b=\frac{1-\sqrt5}{2}

    (So note that a = \phi and b = 1-\phi.)

    Using the usual Partial Fractions technique gives A=B=1

    So we can write L(x) = \frac{1}{1-\phi x}+\frac{1}{1-(1-\phi)x}

    ... and I'll leave it to you to see if you can supply the missing working and finish up.

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Generating functions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 8th 2011, 05:30 AM
  2. Do ratio of consecutive terms converge for ALL linear recursions?
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: December 27th 2010, 10:31 AM
  3. Generating Functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 12th 2010, 05:46 PM
  4. generating functions
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 24th 2009, 08:01 AM
  5. Generating functions...need some help here
    Posted in the Calculus Forum
    Replies: 4
    Last Post: January 31st 2008, 05:32 PM

Search Tags


/mathhelpforum @mathhelpforum