Generating Functions

There is an extremely powerful tool in discrete mathematics used to manipulate sequences called the generating function. The idea is this: instead of an infinite sequence (for example: \(2, 3, 5, 8, 12, \ldots\)) we look at a single function which encodes the sequence. But not a function that gives the \(n\)th term as output. Instead, a function whose power series (like from calculus) displays the terms of the sequence. So for example, we would look at the power series \(2 + 3x + 5x^2 + 8x^3 + 12x^4 + \cdots\) which displays the sequence \(2, 3, 5, 8, 12, \ldots\) as coefficients.

An infinite power series is simply an infinite sum of terms of the form \(c_nx^n\) were \(c_n\) is some constant. So we might write a power series like this: \[\sum_{k=0}^\infty c_k x^k\]. or expanded like this \[c_0 + c_1x + c_2x^2 + c_3x^3 + c_4x^4 + c_5x^5 + \cdots\].

When viewed in the context of generating functions, we call such a power series a generating series. The generating series generates the sequence \[c_0, c_1, c_2, c_3, c_4, c_5, \ldots\].

In other words, the sequence generated by a generating series is simply the sequence of coefficients of the infinite polynomial.

Now you might very naturally ask why we would do such a thing. One reason is that encoding a sequence with a power series helps us keep track of which term is which in the sequence. For example, if we write the sequence \(1, 3, 4, 6, 9, \ldots, 24, 41,\ldots\) it is impossible to determine which term \(24\) is (even if we agreed that the first term was supposed to be \(a_0\)). However, if we wrote the generating series instead, we would have \(1 + 3x + 4x^2 + 6x^3 + 9x^4 + \cdots + 24 x^{17} + 41 x^{18} + \cdots\). Now it is clear that 24 is the 17th term of the sequence (that is, \(a_{17} = 24\)). Of course to get this benefit we could have displayed our sequence in any number of ways, perhaps \(\fbox{1}_0 \fbox{3}_1 \fbox{4}_2 \fbox{6}_3 \fbox{9}_4 \cdots \fbox{24}_{17}\fbox{41}_{18}\cdots\), but we do not do this. The reason is that the generating series looks like an ordinary power series (although we are interpreting it differently) so we can do things with it that we ordinarily do with power series such as write down what it converges to.

For example, from calculus we know that the power series \(1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24} + \cdots + \frac{x^n}{n!} + \cdots\) converges to the function \(e^x\). So we can use \(e^x\) as a way of talking about the sequence of coefficients of the power series for \(e^x\). When we write down a nice compact function which has an infinite power series that we view as a generating series, then we call that function a generating function. In this example, we would say \[1, 1, \frac{1}{2}, \frac{1}{6}, \frac{1}{24}, \ldots, \frac{1}{n!}, \ldots \mbox{ has generating function } e^x\].

The \(e^x\) example is very specific. We have a rather odd sequence, and the only reason we know its generating function is because we happen to know the Taylor series for \(e^x\). Our goal now is to gather some tools to build the generating function of a particular given sequence.

Let's see what the generating functions are for some very simple sequences. The simplest of all: 1, 1, 1, 1, 1, . What does the generating series look like? It is simply \(1 + x + x^2 + x^3 + x^4 + \cdots\). Now, can we find a closed formula for this power series? Yes! This particular series is really just a geometric series with common ratio \(x\). So if we use our multiply, shift and subtract technique from , we have \[\begin{aligned}S \amp = 1 + x + x^2 + x^3 + \cdots \\ \underline{-\qquad xS} \amp \underline{\,\, = ~~~~~~ x + x^2 + x^3 + x^4 + \cdots} \\ (1-x)S \amp = 1\end{aligned}\]

Therefore we see that \[1 + x + x^2 + x^3 \cdots = \dfrac{1}{1-x}\].

You might remember from calculus that this is only true on the interval of convergence for the power series, in this case when \(|x| \lt 1\). That is true for us, but we don't care. We are never going to plug anything in for \(x\), so as long as there is some value of \(x\) for which the generating function and generating series agree, we are happy. And in this case we are happy.

The generating function for \(1,1,1,1,1,1,\ldots\) is \(\dfrac{1}{1-x}\)

Let's use this basic generating function to find generating functions for more sequences. What if we replace \(x\) by \(-x\). We get \[\frac{1}{1+x} = 1 - x + x^2 - x^3 + \cdots \mbox{ which generates } 1, -1, 1, -1, \ldots\].

If we replace \(x\) by \(3x\) we get \[\frac{1}{1-3x} = 1 + 3x + 9x^2 + 27x^3 + \cdots \mbox{ which generates } 1, 3, 9, 27, \ldots\].

By replacing the \(x\) in \(\frac{1}{1-x}\) we can get generating functions for a variety of sequences, but not all. For example, you cannot plug in anything for \(x\) to get the generating function for \(2,2,2,2, \ldots\). However, we are not lost yet. Notice that each term of \(2, 2, 2, 2, \ldots\) is the result of multiplying the terms of \(1, 1, 1, 1, \ldots\) by the constant 2. So multiply the generating function by 2 as well. \[\frac{2}{1-x} = 2 + 2x + 2x^2 + 2x^3 + \cdots \mbox{ which generates } 2, 2, 2, 2, \ldots\].

The generating function for \(1, 2, 3, 4, 5, \ldots\) is \(\d\frac{1}{(1-x)^2}\).

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

We have seen how to find generating functions from \(\frac{1}{1-x}\) using multiplication (by a constant or by \(x\)), substitution, addition, and differentiation. To use each of these, you must notice a way to transform the sequence \(1,1,1,1,1\ldots\) into your desired sequence. This is not always easy. It is also not really the way we have analyzed sequences. One thing we have considered often is the sequence of differences between terms of a sequence. This will turn out to be helpful in finding generating functions as well. The sequence of differences is often simpler than the original sequence. So if we know a generating function for the differences, we would like to use this to find a generating function for the original sequence.

For example, consider the sequence \(2, 4, 10, 28, 82, \ldots\). How could we move to the sequence of first differences: \(2, 6, 18, 54,\ldots\)? We want to subtract 2 from the 4, 4 from the 10, 10 from the 28, and so on. So if we subtract (term by term) the sequence \(0, 2, 4, 10, 28,\ldots\) from \(2, 4, 10, 28\ldots\), we will be set. We can get the generating function for \(0,2,4,10,28,\ldots\) from the generating function for \(2,4,10,28\ldots\) by multiplying by \(x\). Use \(A\) to represent the generating function for \(2, 4, 10, 28, 82, \ldots\) Then: \[\begin{aligned}A \amp = 2 + 4x + 10x^2 +28x^3 + 82x^4 + \cdots \\ \underline{-\qquad xA} \amp \underline{\,\,= 0 + 2x + 4x^2 + 10x^3 + 28 x^4 + 82x^5 + \cdots} \\ (1-x)A \amp = 2 + 2x + 6x^2 + 18x^3 + 54x^4 + \cdots\end{aligned}\]

While we don't get exactly the sequence of differences, we do get something close. In this particular case, we already know the generating function \(A\) (we found it in the previous section) but most of the time we will use this differencing technique to find \(A\): if we have the generating function for the sequence of differences, we can then solve for \(A\).

Now that we have a generating function for the odd numbers, we can use that to find the generating function for the squares:

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

What happens to the sequences when you multiply two generating functions? Let's see: \(A = a_0 + a_1x + a_2x^2 + \cdots\) and \(B = b_0 + b_1x + b_2x^2 + \cdots\). To multiply \(A\) and \(B\), we need to do a lot of distributing (infinite FOIL?) but keep in mind we will group like terms and only need to write down the first few terms to see the pattern. The constant term is \(a_0b_0\). The coefficient of \(x\) is \(a_0b_1 + a_1b_0\). And so on. We get: \[AB = a_0b_0 + (a_0b_1 + a_1b_0)x + (a_0b_2 + a_1b_1 + a_2b_0)x^2 + (a_0b_3 + a_1b_2 + a_2b_1 + a_3b_0)x^3 + \cdots\].

Consider the special case when you multiply a sequence by \(1, 1, 1, \ldots\). For example, multiply \(1,1,1,\ldots\) by \(1, 2, 3, 4, 5\ldots\). The first term is \(1\cdot 1 = 1\). Then \(1\cdot 2 + 1 \cdot 1 = 3\). Then \(1\cdot 3 + 1\cdot 2 + 1 \cdot 1 = 6\). The next term will be 10. We are getting the triangular numbers. More precisely, we get the sequence of partial sums of \(1,2,3,4,5, \ldots\). In terms of generating functions, we take \(\frac{1}{1-x}\) (generating \(1,1,1,1,1\ldots\)) and multiply it by \(\frac{1}{(1-x)^2}\) (generating \(1,2,3,4,5,\ldots\)) and this gives \(\frac{1}{(1-x)^3}\). This should not be a surprise as we found the same generating function for the triangular numbers earlier.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

We conclude with an example of one of the many reasons studying generating functions is helpful. We can use generating functions to solve recurrence relations.

We can now add generating functions to our list of methods for solving recurrence relations.