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

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

and replacing ${\displaystyle x}$ with ${\displaystyle ax}$, we obtain

${\displaystyle G(1;ax)={\frac {1}{1-ax}}=1+(ax)+(ax)^{2}+\cdots +(ax)^{n}+\cdots =\sum _{n=0}^{\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 ${\displaystyle (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 ${\displaystyle {\binom {n}{k}}}$ for all k and n. To do this, consider ${\displaystyle (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 ${\displaystyle a^{n}}$ is just ${\displaystyle 1/(1-ay)}$, the generating function for the binomial coefficients is:

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

and the coefficient on ${\displaystyle x^{k}y^{n}}$ is the ${\displaystyle {\binom {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

${\displaystyle f=\sum _{n\geq 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:

${\displaystyle {\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

${\displaystyle 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

${\displaystyle 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

${\displaystyle f={\frac {1}{\sqrt {5}}}\left({\frac {1}{1-\varphi _{1}x}}-{\frac {1}{1-\varphi _{2}x}}\right).}$

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

${\displaystyle F_{n}={\frac {1}{\sqrt {5}}}(\varphi _{1}^{n}-\varphi _{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

${\displaystyle G(a_{n},x)=\sum _{n=0}^{\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

${\displaystyle G(b_{n},x)=\sum _{n=0}^{\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)