Results 1 to 2 of 2

Math Help - Recurrence relation problem

  1. #1
    Junior Member
    Joined
    Mar 2011
    Posts
    36

    Recurrence relation problem

    Hi I'm studying for my finals and having trouble with this question:

    Consider the following recurrence relation:
    a_{n+2} = a_{n+1} + a_{n} + n for n\geqslant 0 where a_{0} = a_{1} = 1.
    Write the corresponding generating function in its closed form.


    I've set up the generating function as
    G(z) = a_{0} + a_{1}z + a_{2}z^{2} + a_{3}z^{3} + a_{4}z^{4} + ... and I've gotten as far in my working as:
    G(z)(1-z-z^{2})= 1 + nz^{2}(1 + nz + nz^{2} + ...)

    But according to the solutions I should at this stage be getting:
    G(z)(1-z-z^{2})= 1 + z^{3}(1 + 2z + 3z^{2} + ...)

    What am I doing wrong?
    I'd really appreciate some help on this one, thanks in advance!

    Cheers,
    Roro
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,506
    Thanks
    765

    Re: Recurrence relation problem

    We have the following table where I called the function in the last row F(z):

    \begin{array}{cccccc|ccccccc}G(z)      & = & a_0 & + & a_1z^1 & + & a_2z^2 & + & a_3z^3 & + & a_4z^4 & + & \dots\\G(z)z     & = &     &   & a_0z^1 & + & a_1z^2 & + & a_2z^3 & + & a_3z^4 & + & \dots\\G(z)z^2   & = &     &   &        & + & a_0z^2 & + & a_1z^3 & + & a_2z^4 & + & \dots\\F(z)      & = &     &   &        &   & 0z^2  & + & 1z^3   & + & 2z^4   & + & \dots\\\end{array}

    In the right part of the table (after the vertical line), the first row equals the sum of the other rows. Using a_0=a_1=1, this gives

    \begin{aligned}G(z)-1-z &= (G(z)z-z) + G(z)z^2+F(z)\\         &= (G(z)z-z) + G(z)z^2+z^3(1+2z+3z^2+\dots)\\\end{aligned}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. recurrence relation problem!
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 9th 2011, 04:54 PM
  2. Population recurrence relation problem.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 14th 2011, 04:08 AM
  3. Recurrence Relation Problem...
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 10th 2010, 02:41 PM
  4. Recurrence Relation problem (URGENT)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 20th 2010, 03:04 PM
  5. Recurrence relation problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 11th 2008, 10:23 AM

Search Tags


/mathhelpforum @mathhelpforum