Introduction to generating functions
Sequences of numbers appear everywhere throughout computer science and mathematics. One example is the triangular numbers (0, 1, 3, 6, 10, 15, …), where the nth term is described by the equation:
Given a recurrence, is there a way to find a closed-form expression in n that describes the nth term of the sequence? There is more than one answer to this question, but the one we will investigate involves the theory of generating functions.
For example, the sequence consisting of all 1's is represented by the formal sum:
This sum is a geometric series, and can be simplified to the generating function:
NOTE: For readers who are familiar with calculus, the fact that we are working with formal power series and not continuous functions means that we don't have to worry about issues like convergence.
Once we have a generating function, we can use a method such as partial fraction expansion to compute the terms we care about. But is there a more general method for finding a generating function from a recurrence? One way is as follows:
- Multiply both sides of the equation by xⁿ.
- Sum both sides of the equation for all n ≥ 0.
- Rewrite sums to be in the form of the generating function we are looking for, and rename them to A(x).
- Solve the equation for A(x).
To demonstrate how the method works, we'll try it out on the triangular numbers. To simplify things, let's apply the transformations from steps 1-3 to each side separately, and then combine them to perform the final step. Starting with the left-hand side, we have:
The right-hand side simplifies to:
Combining the two and simplifying, we find the generating function we are looking for:
which gives the following formula after partial fraction expansion (omitted):
If you're familiar with other methods of solving recurrences, this approach may seem fairly heavy-handed without much benefit. However, not only do generating functions encompass many different kinds of recurrences, later techniques allow solving a wide variety of counting problems in enumerative combinatorics.
Ordinary generating functions are not the only kind of generating functions. There are several other families, including exponential generating functions and and Dirichlet generating functions. Choosing the right family for a problem can make it much easier to solve. If you're interested in learning more, I recommend checking out the book generatingfunctionology, available for free and in hard copy at major online retailers.
Using the method described in the article, find the generating function for the Fibonacci numbers. Remember that a₀ = 0 and a₁ = 1.
Solution available in paid content section.
No one has reviewed this piece of content yet