# Generating functions and Recurrence relations using the Fibonacci sequence

• Ian_Brooks
In summary, for the given problem, the closed form expression for F(z) is correct and partial fractions are not necessary. For part (b), the expression for A(z) can be found by solving for A(z) using the closed form expression for F(z). In part (c), the partial fraction method can be used to find the explicit form for pn, which is in terms of n, not z. Finally, for part (d), the explicit form for pn can be used to calculate the sum using the formula \sum an = a times \sum bn. It is important to keep track of whether the expression is in terms of n or z throughout the problem.
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 - 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:

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 pn 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!

## 1. What is a generating function?

A generating function is a mathematical tool used to represent a sequence of numbers as a polynomial. It allows us to perform operations on the sequence, such as finding the sum or product of terms, in a more efficient manner.

## 2. How is the Fibonacci sequence related to generating functions?

The Fibonacci sequence is a sequence of numbers where each term is the sum of the two previous terms. This sequence can be represented as a generating function, which allows us to easily calculate terms in the sequence and perform operations on it.

## 3. What is a recurrence relation?

A recurrence relation is a mathematical equation that defines a sequence of numbers by relating each term to one or more previous terms. In the context of the Fibonacci sequence, the recurrence relation is Fn = Fn-1 + Fn-2.

## 4. How can generating functions be used to solve recurrence relations?

Generating functions can be used to solve recurrence relations by converting the relation into a polynomial equation. This allows us to use algebraic techniques to find a closed-form expression for the terms in the sequence.

## 5. What are some applications of generating functions and recurrence relations?

Generating functions and recurrence relations have many applications in mathematics, computer science, and other fields. They can be used to solve problems in combinatorics, analyze algorithms, and model real-world phenomena such as population growth or financial investments.

• Linear and Abstract Algebra
Replies
8
Views
1K
• Calculus and Beyond Homework Help
Replies
13
Views
1K
• Calculus and Beyond Homework Help
Replies
12
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
504
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
7
Views
2K
• Calculus and Beyond Homework Help
Replies
5
Views
2K
• Calculus and Beyond Homework Help
Replies
2
Views
441
• Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
• Calculus and Beyond Homework Help
Replies
7
Views
2K