Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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 (1x)f(x). We have

(1x)f(x)=(1x)(1+x+x2+x3+x4+...)=(1+x+x2+x3+x4+...)(x+x2+x3+x4+x5+...)=1

Dividing through by 1x, we see that f(x)=1(1x).

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(1x), 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(1x), 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. 1,3,5,0,0,0,...
  2. 1,2,22,23,24,...
  3. 1,5,10,15,10,5,1,0,0,0,...
  4. 1,5,10,10,5,1,0,0,0,...

This page titled 7.1: What is a Generating Function? is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Joy Morris.

  • Was this article helpful?

Support Center

How can we help?