Examples of generating functions

The following examples of generating functions are in the spirit of George Pólya, who advocated learning mathematics by doing and re-capitulating as many examples and proofs as possible. The purpose of this article is to present common ways of creating generating functions.

Worked example A: basics

New generating functions can be created by extending simpler generating functions. For example, starting with

$G(1;x)=\sum _{n=0}^{\mathrm{\infty }}{x}^n=\frac{1}{1-x}$

and replacing $x$ with $ax$, we obtain

$G(1;ax)=\frac{1}{1-ax}=1+(ax)+(ax{)}^2+\cdots +(ax{)}^n+\cdots =\sum _{n=0}^{\mathrm{\infty }}{a}^n{x}^n=G(a^n;x).$

Bivariate generating functions

One can define generating functions in several variables, for series with several indices. These are often called super generating functions, and for 2 variables are often called bivariate generating functions.

For instance, since $(1+x{)}^n$ is the generating function for binomial coefficients for a fixed n, one may ask for a bivariate generating function that generates the binomial coefficients $(\genfrac{}{}{0ex}{}{n}{k})$ for all k and n. To do this, consider $(1+x{)}^n$ as itself a series (in n), and find the generating function in y that has these as coefficients. Since the generating function for $a^n$ is just $1/(1-ay)$, the generating function for the binomial coefficients is:

$\frac{1}{1-(1+x)y}=1+(1+x)y+(1+x{)}^2{y}^2+\dots ,$

and the coefficient on $x^k{y}^n$ is the $(\genfrac{}{}{0ex}{}{n}{k})$ binomial coefficient.

Worked example B: Fibonacci numbers

Consider the problem of finding a closed formula for the Fibonacci numbers F_n defined by F₀ = 0, F₁ = 1, and F_n = F_n−1 + F_n−2 for n ≥ 2. We form the ordinary generating function

$f=\sum _{n\ge 0}{F}_n{x}^n$

for this sequence. The generating function for the sequence (F_n−1) is xf and that of (F_n−2) is x²f. From the recurrence relation, we therefore see that the power series xf + x²f agrees with f except for the first two coefficients:

$\begin{array}{rcrcrcrcrcrcr}f& =& F_0{x}^0& +& F_1{x}^1& +& F_2{x}^2& +& \cdots & +& F_i{x}^i& +& \cdots \\ xf& =& & & F_0{x}^1& +& F_1{x}^2& +& \cdots & +& F_{i-1}{x}^i& +& \cdots \\ x^{2}f& =& & & & & F_0{x}^2& +& \cdots & +& F_{i-2}{x}^i& +& \cdots \\ (x+x^2)f& =& & & F_0{x}^1& +& (F_0+F_1)x^2& +& \cdots & +& (F_{i-1}+F_{i-2})x^i& +& \cdots \\ & =& & & & & F_2{x}^2& +& \cdots & +& F_i{x}^i& +& \cdots \\ \end{array}$

Taking these into account, we find that

$f=xf+x^{2}f+x.$

(This is the crucial step; recurrence relations can almost always be translated into equations for the generating functions.) Solving this equation for f, we get

$f=\frac{x}{1-x-x^2}.$

The denominator can be factored using the golden ratio φ₁ = (1 + √5)/2 and φ₂ = (1 − √5)/2, and the technique of partial fraction decomposition yields

$f=\frac{1}{\sqrt{5}}(\frac{1}{1-{\phi }_{1}x}-\frac{1}{1-{\phi }_{2}x}).$

These two formal power series are known explicitly because they are geometric series; comparing coefficients, we find the explicit formula

$F_n=\frac{1}{\sqrt{5}}({\phi }_1^n-{\phi }_2^n).$

Worked example C: Number of ways to make change

The number of unordered ways a_n to make change for n cents using coins with values 1, 5, 10, and 25 is given by the generating function

$G(a_n,x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n=\frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})}.$

For example there are two unordered ways to make change for 6 cents; one way is six 1-cent coins, the other way is one 1-cent coin and one 5-cent coin. See OEIS: A001299.

On the other hand, the number of ordered ways b_n to make change for n cents using coins with values 1, 5, 10, and 25 is given by the generating function

$G(b_n,x)=\sum _{n=0}^{\mathrm{\infty }}{b}_n{x}^n=\frac{1}{1-x-x^5-x^{10}-x^{25}}.$

For example there are three ordered ways to make change for 6 cents; one way is six 1-cent coins, a second way is one 1-cent coin and one 5-cent coin, and a third way is one 5-cent coin and one 1-cent coin. Compare to OEIS: A114044, which differs from this example by also including coins with values 50 and 100.

External links

• Generating Functions, Power Indices and Coin Change at cut-the-knot
• Generatingfunctionology (PDF)