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

## Contents

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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G(a_n;x)=\sum_{n=0}^{\infty}a_nx^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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G(a_{m,n};x,y)=\sum_{m,n=0}^{\infty}a_{m,n}x^my^n.}**

### Exponential generating function

The *exponential generating function* of a sequence *a*_{n} is

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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*^{2} are:

### Ordinary generating function

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G(n^2;x)=\sum_{n=0}^{\infty}n^2x^n=\frac{x(x+1)}{(1-x)^3}}**

### Exponential generating function

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle EG(n^2;x)=\sum _{n=0}^{\infty} \frac{n^2x^n}{n!}=x(x+1)e^x}**

### Bell series

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_p(x)=\sum_{n=0}^\infty p^{2n}x^n=\frac{1}{1-p^2x}}**

### Dirichlet series generating function

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G(1;x)=\sum_{n=0}^{\infty} x^n = \frac{1}{1-x}}**

and replacing **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x}**
with **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2x}**
, we obtain

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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} = 0, *f*_{1} = 1, and *f*_{n} = *f*_{n−1} + *f*_{n−2} for *n* ≥ 2. We form the ordinary generating function

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f = \sum_{n \ge 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*^{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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f = \frac{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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

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

fr:Fonction génératrice he:פונקציה יוצרת it:Funzione generatrice ru:Производящая функция