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

1. May 5, 2010

### Ian_Brooks

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 ($$\sum$$ (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