# Definition:Generating Function

## Definition

Let $A = \left \langle {a_n}\right \rangle$ be a sequence in $\R$.

Then $\displaystyle G_A \left({z}\right) = \sum_{n \mathop \ge 0} a_n z^n$ is called the generating function for the sequence $A$.

The mapping $G_A \left({z}\right)$ is defined for all $z$ for which the power series $\displaystyle \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 $G \left({z}\right)$ be the generating function for the sequence $S = \left\langle{a_n}\right\rangle$.

The coefficient of $z^n$ extracted from $G \left({z}\right)$ is the $n$th term of $S$, and can be denoted:

$\left[{z^n}\right] G \left({z}\right) := a_n$

## Doubly Subscripted Sequence

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

Then $\displaystyle G_A \left({w, z}\right) = \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, $G \left({z}\right)$ 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