- #1

- 128

- 0

## 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

^{2})

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

^{2}) = a

_{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 - 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?}