# Definition:Generating Function

## Definition

Let $A = \sequence {a_n}$ be a sequence in $\R$.

Then $\ds \map {G_A} z = \sum_{n \mathop \ge 0} a_n z^n$ is called the **generating function** for the sequence $A$.

The mapping $\map {G_A} z$ is defined for all $z$ for which the power series $\ds \sum_{n \mathop \ge 0} a_n z^n$ is convergent.

The definition can be modified so that the lower limit of the summation is $b$ where $b > 0$ by assigning $a_k = 0$ where $0 \le k < b$.

### Parameter

Let $G_A \left({z}\right)$ be a **generating function** for the sequence $A$.

The variable $z$ is a dummy variable, known as the **parameter** of $G_A \left({z}\right)$.

### Extraction of Coefficient

Let $\map G z$ be the generating function for the sequence $S = \sequence {a_n}$.

The **coefficient of $z^n$ extracted from $\map G z$** is the $n$th term of $S$, and can be denoted:

- $\sqbrk {z^n} \map G z := a_n$

## Doubly Subscripted Sequence

Let $A = \sequence {a_{m, n} }$ be a doubly subscripted sequence in $\R$ for $m, n \in \Z_{\ge 0}$.

Then $\ds \map {G_A} {w, z} = \sum_{m, \, n \mathop \ge 0} a_{m n} w^m z^n$ is called the **generating function** for the sequence $A$.

## Also denoted as

When the sequence is understood, $\map G z$ can be used.

Different authors may use different symbols.

The symbol used for the **parameter** varies.

$x$ is often used instead.

In the field of probability theory $s$ tends to be the symbol of choice.

Some authors use $\zeta$.

## Also see

- Results about
**generating functions**can be found here.

## Historical Note

Generating functions were introduced by Abraham de Moivre to solve the general problem of linear recurrences.

James Stirling then extended this theory in his *Methodus Differentialis* of $1730$, by using differentiation and integration.

Then Leonhard Paul Euler began extending their use to new fields such as combinatorics.

Pierre-Simon de Laplace took the technique into the field of probability theory in his $1812$ work *Théorie Analytique des Probabilités*

Many others since have developed the technique further.

*A generating function is a clothesline on which we hang up a sequence of numbers for display.*- -- 1990: Herbert S. Wilf:
*generatingfunctionology*

- -- 1990: Herbert S. Wilf:

## Sources

- 1956: G. Pólya:
*On Picture-Writing*(*Amer. Math. Monthly***Vol. 63**: pp. 689 – 697) www.jstor.org/stable/2309555 - 1971: George E. Andrews:
*Number Theory*... (previous) ... (next): $\text {3-4}$ Generating Functions: Definition $\text {3-3}$ - 1986: Geoffrey Grimmett and Dominic Welsh:
*Probability: An Introduction*... (previous) ... (next): $\S 4.1$: Generating functions - 1990: Herbert S. Wilf:
*generatingfunctionology* - 1994: Ronald L. Graham, Donald E. Knuth and Oren Patashnik:
*Concrete Mathematics: A Foundation for Computer Science*(2nd ed.) $\S 1.2$ - 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.8$: Fibonacci Numbers - 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.9$: Generating Functions: $(1)$