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