# Generating function

In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an 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 an is

$\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 an 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 am,n (where n and m are natural numbers) is

$\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 an is

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

### Lambert series

The Lambert series of a sequence an is

$\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

$\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 an is

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

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

$\displaystyle DG(a_n;s)=\prod_{p} f_p(p^{-s}).$

If an 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

$\displaystyle e^{xf(t)}=\sum_{n=0}^\infty {p_n(x) \over n!}t^n$

where pn(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 an = n2 are:

### Ordinary generating function

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

### Exponential generating function

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

### Bell series

$\displaystyle f_p(x)=\sum_{n=0}^\infty p^{2n}x^n=\frac{1}{1-p^2x}$

### Dirichlet series generating function

$\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

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

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

$\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 fn defined by f0 = 0, f1 = 1, and fn = fn−1 + fn−2 for n ≥ 2. We form the ordinary generating function

$\displaystyle f = \sum_{n \ge 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. Taking these into account, we find that

$\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

$\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

$\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

$\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.
The text passage provides an extensive overview of generating functions in mathematics, including definitions, types, and examples. It does not contain any specific mathematical questions or answers to such questions.
no_question
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Generating function

In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an 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 an is

$\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 an 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 am,n (where n and m are natural numbers) is

$\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 an is

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

### Lambert series

The Lambert series of a sequence an is

$\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

$\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 an is

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

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

$\displaystyle DG(a_n;s)=\prod_{p} f_p(p^{-s}).$

If an 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

$\displaystyle e^{xf(t)}=\sum_{n=0}^\infty {p_n(x) \over n!}t^n$

where pn(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 an = n2 are:

### Ordinary generating function

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

### Exponential generating function

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

### Bell series

$\displaystyle f_p(x)=\sum_{n=0}^\infty p^{2n}x^n=\frac{1}{1-p^2x}$

### Dirichlet series generating function

$\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

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

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

$\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 fn defined by f0 = 0, f1 = 1, and fn = fn−1 + fn−2 for n ≥ 2. We form the ordinary generating function

$\displaystyle f = \sum_{n \ge 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. Taking these into account, we find that

$\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

$\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

$\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

$\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.
user
The text passage provides an extensive overview of generating functions in mathematics, including definitions, types, and examples. It does not contain any specific mathematical questions or answers to such questions.

TYPE: NO_QUESTION