# 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 $\map {G_A} z$ be a generating function for the sequence $A$.

The variable $z$ is a dummy variable, known as the parameter of $\map {G_A} z$.

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