Formal power series and non/homogeneous recurrence relations

[Ian_Brooks]

Homework Statement

Homework Equations

We're using generating functions, and recurrence relations of homogeneous and non-homogeneous types

The mark allocation is 2, 3, 3 and 2

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 - z²)

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 + z²) = a<sub>0 + 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 - z²) (1-z)²) ]

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 + z²) = a0 + z (a1 - 2a0) + z² (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 (n², 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 (\sum ^(n+k)Ck z² ) (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?</sub>

 

[lanedance]

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

 

[lanedance]

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

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 a_j that may be easier to solve...