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 - 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.

Table of contents

1 Definitions 1.1 Ordinary generating function 1.2 Exponential generating function 1.3 Dirichlet series generating functions 2 Examples 2.4 Ordinary generating function 2.5 Exponential generating function 2.6 Dirichlet series generating function 3 Uses 4 See also 5 References

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

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_n^m (where n and m are natural numbers) is

Exponential generating function

The exponential generating function of a sequence a_n is

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

Dirichlet series generating functions are especially useful for multiplicative functions, when they have an Euler product expression. If a_n is a Dirichlet character then its Dirichlet series generating function is called a Dirichlet L-series.

Examples

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

Ordinary generating function

Exponential generating function

Dirichlet series generating function

Uses

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

• See formal power series for an example using the generating function of Fibonacci numbers
• Moment-generating function
• Probability-generating function

---

References

• Wilf, Herbert S. (1994) generatingfunctionology (Second Edition). Academic Press. ISBN 0127519564. For a downloadable version provided by Herbert Wilf and Academic Press, see this link: Download the book Generatingfunctionology