Introduction to generating functions
Overview[edit | edit source]
The main idea here is that we're going to work in the ring of formal power series. A ring, recall, is just a certain type of algebraic structure. For us, all we need to concern ourselves with right now is that the sum of two power series is a power series and that the product of two power series is a power series. Every power series has an additive inverse (almost trivially), and some have multiplicative inverses (which will be discussed in later sections). The most important thing to remember is that we consider these power series as elements of a certain ring. As such, we are not concerned with the convergence of any power series (yet). There will come a time and place to discuss these ideas (as we will want to sum certain sequences and pick off certain terms, both of which demand us "plugging in values for x"), but for now, we'll just interpret them formally.
As a brief example, note that the expression does not have a positive radius of convergence (converges only when x = 0), but it is still a perfectly good element of our ring of formal power series.
Types of generating functions[edit | edit source]
Ordinary generating functions[edit | edit source]
Given a sequence , the ordinary generating function of f(x) is the formal power series
If f(x) is the ordinary generating function for the sequence , we often write
We don't often concern ourselves with the convergence of these series; we interpret them strictly in a formal sense.
For an example, recall from calculus that the function has power series representation
The sequence of coefficients of the powers of x in the above power series is the sequence that is constantly 1. Hence, we have that
Exponential generating functions[edit | edit source]
Another type of generating function, the exponential generating function is similar to the ordinary generating function, but with a twist. If f(x) is the exponential generating function for the sequence , we write
and this means that the function f(x) has power series representation
We saw above that the function is the ordinary generating function for the sequence that is constantly 1; but for what sequence is it the exponential generating function?
Note that for all n, we have
If we set , we have that
so we can write
So what is the exponential generating function of the sequence that is constantly 1? Recall that ex has the power series representation
so we have
This should give you a feel as to why the name for such a generating function is "exponential" generating function.
Continuation[edit | edit source]
This lesson continues on the page titled calculus of generating functions.