# Examples of generating functions

*https://en.wikipedia.org/wiki/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

and replacing with , 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 is the generating function for
binomial coefficients for a fixed *n,* one may ask for a bivariate generating function that generates the binomial coefficients for all *k* and *n.*
To do this, consider as *itself* a series (in *n*), and find the generating function in *y* that has these as coefficients. Since the generating function for is just , the generating function for the binomial coefficients is:

and the coefficient on is the 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 + √5)/2 and φ_{2} = (1 − √5)/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 *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

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

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.