Definition:Generating Function

From ProofWiki
Jump to: navigation, search


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


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