Forest Belton spent #science

# Introduction to generating functions

1yr ago 10.0¢

Forest Belton spent #science

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:

This equation is known as a recurrence. Another example is the Fibonacci numbers (0, 1, 1, 2, 3, 5, …), given by the recurrence:

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.

## Generating functions

If a function f(x) can be represented as a formal power series in x, with a_n being the coefficient of xⁿ, then f(x) is called the (ordinary) generating function of a_n. In other words, f(x) must satisfy:

For example, the sequence consisting of all 1's is represented by the formal sum:

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):

## Final thoughts

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.

## Exercise

Using the method described in the article, find the generating function for the Fibonacci numbers. Remember that a₀ = 0 and a₁ = 1.

## Solution

Solution available in paid content section.

No one has reviewed this piece of content yet