Generating function

In mathematics a generating function is a formal power series whose coefficients encode information about a sequence a_n that is indexed by the natural numbers.

There are various types of generating functions, including ordinary generating functions, exponential generating functions, Lambert series, Bell series, and Dirichlet series; definitions and examples are given below. Every sequence has a generating function of each type. The particular generating function that is most useful in a given context will depend upon the nature of the sequence and the details of the problem being addressed.

Generating functions are often expressed in closed form as functions of a formal argument x. Sometimes a generating function is evaluated at a specific value of x. However, it must be remembered that generating functions are formal power series, and they will not necessarily converge for all values of x.

Definitions

A generating function is a clothesline on which we hang up a sequence of numbers for display.

— Herbert Wilf, generatingfunctionology (1994)

Ordinary generating function

The ordinary generating function of a sequence a_n is

$G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.$

When generating function is used without qualification, it is usually taken to mean an ordinary generating function.

If a_n is the probability mass function of a discrete random variable, then its ordinary generating function is called a probability-generating function.

The ordinary generating function can be generalised to sequences with multiple indexes. For example, the ordinary generating function of a sequence a_m,n (where n and m are natural numbers) is

$G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}.$

Exponential generating function

The exponential generating function of a sequence a_n is

$EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.$

Lambert series

The Lambert series of a sequence a_n is

$LG(a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}.$

Note that in a Lambert series the index n starts at 1, not at 0.

Bell series

The Bell series of an arithmetic function f(n) and a prime p is

$f_{p}(x)=\sum _{n=0}^{\infty }f(p^{n})x^{n}.$

Dirichlet series generating functions

Dirichlet series are often classified as generating functions, although they are not strictly formal power series. The Dirichlet series generating function of a sequence a_n is

$DG(a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}.$

The Dirichlet series generating function is especially useful when a_n is a multiplicative function, when it has an Euler product expression in terms of the function's Bell series

$DG(a_{n};s)=\prod _{p}f_{p}(p^{-s}).$

If a_n is a Dirichlet character then its Dirichlet series generating function is called a Dirichlet L-series.

Polynomial sequence generating functions

The idea of generating functions can be extended to sequences of other objects. Thus, for example, polynomial sequences of binomial type are generated by

$e^{xf(t)}=\sum _{n=0}^{\infty }{p_{n}(x) \over n!}t^{n}$

where p_n(x) is a sequence of polynomials and f(t) is a function of a certain form. Sheffer sequences are generated in a similar way. See the main article generalized Appell polynomials for more information.

Examples

Generating functions for the sequence of square numbers a_n = n² are:

Ordinary generating function

$G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {x(x+1)}{(1-x)^{3}}}$

Exponential generating function

$EG(n^{2};x)=\sum _{n=0}^{\infty }{\frac {n^{2}x^{n}}{n!}}=x(x+1)e^{x}$

Bell series

$f_{p}(x)=\sum _{n=0}^{\infty }p^{2n}x^{n}={\frac {1}{1-p^{2}x}}$

Dirichlet series generating function

$DG(n^{2};s)=\sum _{n=1}^{\infty }{\frac {n^{2}}{n^{s}}}=\zeta (s-2)$

Another example

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

$G(1;x)=\sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}$

and replacing $x$ with $2x$, we obtain

$G(1;2x)={\frac {1}{1-2x}}=1+(2x)+(2x)^{2}+\ldots +(2x)^{n}+\ldots =G(2^{n};x).$

More detailed example — Fibonacci numbers

Consider the problem of finding a closed formula for the Fibonacci numbers f_n defined by f₀ = 0, f₁ = 1, and f_n = f_n−1 + f_n−2 for n ≥ 2. We form the ordinary generating function

$f=\sum _{n\geq 0}f_{n}X^{n}$

for this sequence. The generating function for the sequence (f_n−1) is Xf and that of (f_n−2) is X²f. From the recurrence relation, we therefore see that the power series Xf + X²f agrees with f except for the first two coefficients. Taking these into account, we find that

$f=Xf+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={\frac {X}{1-X-X^{2}}}$

The denominator can be factored using the golden ratio φ₁ = (1 + √5)/2 and φ₂ = (1 − √5)/2, and the technique of partial fraction decomposition yields

$f={\frac {1/{\sqrt {5}}}{1-\phi _{1}X}}-{\frac {1/{\sqrt {5}}}{1-\phi _{2}X}}$

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

$f_{n}={\frac {1}{\sqrt {5}}}(\phi _{1}^{n}-\phi _{2}^{n}).$

Applications

Generating functions are used to

• Find recurrence relations for sequences – the form of a generating function may suggest a recurrence formula.
• Find relationships between sequences – if the generating functions of two sequences have a similar form, then the sequences themselves are probably related.
• Explore the asymptotic behaviour of sequences.
• Prove identities involving sequences.
• Solve enumeration problems in combinatorics.
• Evaluate infinite sums.

See also

• Moment-generating function
• Probability-generating function
• Stanley's reciprocity theorem

References

• Herbert S. Wilf, Generatingfunctionology (Second Edition) (1994) Academic Press. ISBN 0127519564.

• Donald E. Knuth, The Art of Computer Programming, Volume 1 Fundamental Algorithms (Third Edition) Addison-Wesley. ISBN 020189683-4 (Generating functions are discussed in section 1.2.9.)

External links

• Generating Functions, Power Indices and Coin Change
• Generatingfunctionology (PDF)