Introduction to generating functions

Overview

edit

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

Ordinary generating functions

edit

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

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

This lesson continues on the page titled calculus of generating functions.

See also

edit