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.[citation needed] 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
- [math]\displaystyle{ G(1;x)=\sum_{n=0}^{\infty} x^n = \frac{1}{1-x} }[/math]
and replacing [math]\displaystyle{ x }[/math] with [math]\displaystyle{ ax }[/math], we obtain
- [math]\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). }[/math]
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 [math]\displaystyle{ (1+x)^n }[/math] is the generating function for binomial coefficients for a fixed n, one may ask for a bivariate generating function that generates the binomial coefficients [math]\displaystyle{ \binom{n}{k} }[/math] for all k and n. To do this, consider [math]\displaystyle{ (1+x)^n }[/math] as itself a series (in n), and find the generating function in y that has these as coefficients. Since the generating function for [math]\displaystyle{ a^n }[/math] is just [math]\displaystyle{ 1/(1-ay) }[/math], the generating function for the binomial coefficients is:
- [math]\displaystyle{ \frac{1}{1-(1+x)y}=1+(1+x)y+(1+x)^2y^2+\dots, }[/math]
and the coefficient on [math]\displaystyle{ x^ky^n }[/math] is the [math]\displaystyle{ \binom{n}{k} }[/math] binomial coefficient.
Worked example B: Fibonacci numbers
Consider the problem of finding a closed formula for the Fibonacci numbers Fn defined by F0 = 0, F1 = 1, and Fn = Fn−1 + Fn−2 for n ≥ 2. We form the ordinary generating function
- [math]\displaystyle{ f = \sum_{n \ge 0} F_n x^n }[/math]
for this sequence. The generating function for the sequence (Fn−1) is xf and that of (Fn−2) is x2f. From the recurrence relation, we therefore see that the power series xf + x2f agrees with f except for the first two coefficients:
- [math]\displaystyle{ \begin{array}{rcrcrcrcrcrcr} f & = & F_0x^0 & + & F_1x^1 & + & F_2x^2 & + & \cdots & + & F_ix^i & + &\cdots\\ xf & = & & & F_0x^1 & + & F_1x^2 & + & \cdots & + &F_{i-1}x^i & + &\cdots\\ x^2f & = & & & & & F_0x^2 & + & \cdots & + &F_{i-2}x^i & +&\cdots\\ (x+x^2)f & = & & & F_0x^1 & + & (F_0+F_1)x^2 & + & \cdots & + & (F_{i-1}+F_{i-2})x^i & +&\cdots\\ & = & & & & & F_2x^2 & + & \cdots & + & F_ix^i & +& \cdots\\ \end{array} }[/math]
Taking these into account, we find that
- [math]\displaystyle{ f = xf + x^2 f + x . }[/math]
(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
- [math]\displaystyle{ f = \frac{x} {1 - x - x^2} . }[/math]
The denominator can be factored using the golden ratio φ1 = (1 + √5)/2 and φ2 = (1 − √5)/2, and the technique of partial fraction decomposition yields
- [math]\displaystyle{ f = \frac{1}{\sqrt{5}} \left (\frac{1}{1-\varphi_1 x} - \frac{1} {1- \varphi_2 x} \right ) . }[/math]
These two formal power series are known explicitly because they are geometric series; comparing coefficients, we find the explicit formula
- [math]\displaystyle{ F_n = \frac{1} {\sqrt{5}} (\varphi_1^n - \varphi_2^n). }[/math]
Worked example C: Number of ways to make change
The number of unordered ways an to make change for n cents using coins with values 1, 5, 10, and 25 is given by the generating function
- [math]\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})}\,. }[/math]
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 bn to make change for n cents using coins with values 1, 5, 10, and 25 is given by the generating function
- [math]\displaystyle{ G(b_n, x) = \sum_{n=0}^\infty b_n x^n = \frac{1}{1-x-x^5-x^{10}-x^{25}}\,. }[/math]
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
 |
