Harman Patil (Editor)

Examples of generating functions

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

Worked example A: basics

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

G ( 1 ; x ) = ∑ n = 0 ∞ x n = 1 1 − x

and replacing x with a x , we obtain

G ( 1 ; a x ) = 1 1 − a x = 1 + ( a x ) + ( a x ) 2 + ⋯ + ( a x ) n + ⋯ = ∑ n = 0 ∞ 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 ( 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 ( n k ) for all k and n. To do this, consider ( 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 a n is just 1 / ( 1 − a y ) , the generating function for the binomial coefficients is:

1 1 − ( 1 + x ) y = 1 + ( 1 + x ) y + ( 1 + x ) 2 y 2 + … ,

and the coefficient on x k y n is the ( n k ) 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

f = ∑ n ≥ 0 F n x n

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:

f = F 0 x 0 + F 1 x 1 + F 2 x 2 + ⋯ + F i x i + ⋯ x f = F 0 x 1 + F 1 x 2 + ⋯ + F i − 1 x i + ⋯ x 2 f = F 0 x 2 + ⋯ + F i − 2 x i + ⋯ ( x + x 2 ) f = F 0 x 1 + ( F 0 + F 1 ) x 2 + ⋯ + ( F i − 1 + F i − 2 ) x i + ⋯ = F 2 x 2 + ⋯ + F i x i + ⋯

Taking these into account, we find that

f = x f + 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

f = x 1 − x − x 2 .

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

f = 1 5 ( 1 1 − φ 1 x − 1 1 − φ 2 x ) .

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

F n = 1 5 ( φ 1 n − φ 2 n ) .

References

Examples of generating functions Wikipedia
(Text) CC BY-SA