7.1: What is a Generating Function?
( \newcommand{\kernel}{\mathrm{null}\,}\)
A generating function is a formal structure that is closely related to a numerical sequence, but allows us to manipulate the sequence as a single entity, with the goal of understanding it better. Here’s the formal definition.
Definition: Generating Function
For a sequence a0,a1,...,an,... the corresponding generating function f(x) is the series
f(x)=a0+a1x+...+anxn+...=∞∑i=0aixi
So an, the nth term of the sequence, is the coefficient of xn in f(x).
Example 7.1.1
Here are a number of basic examples.
1) 1,1,1,1,1,1,0,0,0,... has generating function
1+x+x2+x3+x4+x5
2) 1,4,6,4,1,0,0,0,... has generating function
1+4x+6x2+4x3+x4=(1+x)4
3) (n0),(n1),...,(nn),0,0,0,... has generating function
(n0)+(n1)x+...+(nn)xn=(1+x)n
4) 1,1,1,1,... has generating function
f(x)=1+x+x2+x3+...=∞∑i=0xi
These generating functions can be manipulated. For example, if f(x) is as in Example 7.1.2 (4), suppose we take the product (1−x)f(x). We have
(1−x)f(x)=(1−x)(1+x+x2+x3+x4+...)=(1+x+x2+x3+x4+...)−(x+x2+x3+x4+x5+...)=1
Dividing through by 1−x, we see that f(x)=1(1−x).
This may seem artificial and rather nonsensical since the generating function was defined as a formal object whose coefficients are a sequence that interests us. In fact, although we won’t delve into the formalities in this course, algebraic manipulation of generating functions can be formally defined, and gives us exactly these results.
A reasonable question at this point might be, what use is this? Even if we agree that f(x)=1(1−x), what we really want is the coefficient of xn (in order to retrieve an, the nth term of our sequence). If we have an expression like 1(1−x), how can we work out the coefficient of xn?
Exercise 7.1.1
For each of the following sequences, give the corresponding generating function.
- 1,3,5,0,0,0,...
- 1,2,22,23,24,...
- 1,5,10,15,10,5,1,0,0,0,...
- 1,5,10,10,5,1,0,0,0,...