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!

Homework Help: Generating functions and Recurrence relations using the Fibonacci sequence

  1. May 5, 2010 #1
    We're using generating functions, and recurrence relations of homogeneous and non-homogeneous types

    The mark allocation is 2, 3, 3 and 2

    3. The attempt at a solution

    I think I've done the first part correctly. The closed form is in terms of z, right? I get:

    F(z) = z / (1 - z - z2)

    but I'm unsure if I have to go into partial fractions for this in my answer. For part b, I get:

    A(z)(1 - 2z + z2) = a0 + z(a1 - 2a0) ...
    = F(z)
    so I take my closed formula from part a and substitute F(z) for it so I get

    A(z) = z / [ (1 - z - z2) (1-z)2) ]

    I'm still unsure if this is right, since looking at previous examples, they express A(z) in terms of itself, that is: group together coefficients of an etc. and get a more complex remainder; They suggest to do this:

    A(z)(1 - 2z + z2) = a0 + z (a1 - 2a0) + z2 (a2 -2a1 + a0) ...

    and group together the coefficients of a1 or a2 etc. so there is a generating function within the brackets. I used F(z) in this case, but is that really in terms of itself?

    For part (c), I want to use the bn and pn way for non homogeneous recurrence relations, but I got lost; we've only gone over the pn being a power of n (n2, n or even just integers) but the function here, even in the explicit form, is an integer to the power of n (I solved the Fibonacci sequence via the polynomial method). I used the partial fraction method, but it ended up very ugly, substituting alpha for (1 - root5 / 2) and beta for (1 - alpha), their product as negative 1, and their sum as positive 1. This is only a three mark question, and my working is over 3 pages, incomplete. Even if I finish it, I don't remember how to get from the closed form to explicit (that's in terms of n, right?). I can use a/(1-bz) = a times bn , but what about with multiple powers of (1-z) at the denominator? I only recall the generating function version of that ([tex]\sum[/tex] (n+k)Ck z2 ) (bounds from n=0 to infinity), but not in it's explicit form.

    Then for part (d), I'm unsure how to use part (c) to calculate the sum as I am completely lost for it. Any pointers?
    Last edited: May 5, 2010
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted