Definition:Generating Function

From ProofWiki
Jump to navigation Jump to search

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 bound 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, the notation $\map G z$ can be used for its generating function.

Different authors may use different symbols for $G_A$, for example:

$\map {f_A} z$
$\map U s$
$\map A x$
$\map {\mathrm f} t$


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$, and some use $t$.


Also known as

A generating function is also known as an enumerating series, particularly in problems of combinatorics.


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


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Generating_Function&oldid=682288"