Examples of generating functions

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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

and replacing with , we obtain

Bivariate generating functions[edit]

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[edit]

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

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:

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

External links[edit]