Generating functions and Recurrence relations using the Fibonacci sequence

[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

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>

 

[mighty2000]

Thank you for sharing your thought process and working through the problem. It seems like you have a good understanding of generating functions and recurrence relations, but there are a few areas that may need clarification.

Firstly, for part (a), your closed form expression for F(z) is correct. You do not need to go into partial fractions for this problem, as the expression is already in its simplest form. However, if the expression was more complex, partial fractions may be necessary to simplify it further.

For part (b), you are correct in using the closed form expression for F(z) to find A(z). However, it is not necessary to group together coefficients of a1 or a2, as you have done. You can simply use the expression for F(z) and solve for A(z) by multiplying both sides by (1-2z+z2). This will give you the explicit form for A(z).

For part (c), you are on the right track by using the bn and p<sub>n method for solving non-homogeneous recurrence relations. It is important to note that pn does not have to be a power of n, it can be any function of n. In this case, you can use the partial fraction method to simplify the expression and then use the formula a/(1-bz) = a times bn to find the explicit form for pn. Remember that the explicit form is in terms of n, not z.

Finally, for part (d), you can use the explicit form for pn that you found in part (c) to calculate the sum using the formula \sum an = a times \sum bn. Again, remember to express the sum in terms of n, not z.

I hope this helps clarify any confusion you may have had with the problem. Keep up the good work with generating functions and recurrence relations!</sub>