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
and replacing formula_2 with formula_3, we obtain
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 formula_5 is the generating function for binomial coefficients for a fixed "n," one may ask for a bivariate generating function that generates the binomial coefficients formula_6 for all "k" and "n."
To do this, consider formula_5 as "itself" a series (in "n"), and find the generating function in "y" that has these as coefficients. Since the generating function for formula_8 is just formula_9, the generating function for the binomial coefficients is:
and the coefficient on formula_11 is the formula_6 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 = 0, "F"1 = 1, and "F""n" = "F""n"−1 + "F""n"−2 for "n" ≥ 2. We form the ordinary generating function
for this sequence. The generating function for the sequence ("F""n"−1) is "xf" and that of ("F""n"−2) is "x"2"f". From the recurrence relation, we therefore see that the power series "xf" + "x"2"f" agrees with "f" except for the first two coefficients:
Taking these into account, we find that
(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
The denominator can be factored using the golden ratio φ1 = (1 + )/2 and φ2 = (1 − )/2, and the technique of partial fraction decomposition yields
These two formal power series are known explicitly because they are geometric series; comparing coefficients, we find the explicit formula
Worked example C: Number of ways to make change.
The number of ways "a""n" to make change for "n" cents using coins with values 1, 5, 10, and 25 is given by the generating function
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 .
On the other hand, the number of ways "b""n" to make change for "n" cents using coins with values 1, 5, 10, and 25 is given by the generating function
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 , which differs from this example by also including coins with values 50 and 100.