Introduction to generating functions

From Wikiversity
Jump to navigation Jump to search

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.