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: Formal power series and non/homogeneous recurrence relations

  1. May 5, 2010 #1
    1. The problem statement, all variables and given/known data


    2. Relevant equations

    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?
  2. jcsd
  3. May 5, 2010 #2


    User Avatar
    Homework Helper

    i'd agree with a) & b) and think you're essentially doing the same thing as the solution

    for d) try writing out an in terms of the Fj's and see if you can spot a pattern
    Last edited: May 5, 2010
  4. May 5, 2010 #3


    User Avatar
    Homework Helper

    for c) you want to try and probably get rid of the F term so how about looking at
    [tex] a_{n+1}-a_n{n} [/tex]

    after manipulation, this should leave you with an equation with a negative F term. Then adding that to the original, with correct choice of index, should leave you with a pure recurrence relation of aj that may be easier to solve...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook