Generating function

In different areas of mathematics , the generating function of a sequence is understood to be the formal power series ${\displaystyle (a_{n})}$

${\displaystyle f(z)=\sum _{n=0}^{\infty }a_{n}z^{n}}$.

For example, the generating function of the constant sequence is the geometric series ${\displaystyle 1,1,1,\ldots }$

${\displaystyle f(z)=\sum _{n=0}^{\infty }z^{n}=1z^{0}+1z^{1}+1z^{2}+\ldots }$

The series converges for all and has value ${\displaystyle |z|<1}$

${\displaystyle f(z)={\frac {1}{1-z}}}$.

Because of the use of formal power series, however, questions of convergence do not generally play a role - it is just a symbol. This more explicit representation as a power series often allows conclusions to be drawn about the consequence. ${\displaystyle z}$

Examples

The following identities apply:

• ${\displaystyle \sum _{n=0}^{\infty }nz^{n}={\frac {z}{(1-z)^{2}}}}$     (generating function of the sequence of natural numbers ) ${\displaystyle 0,1,2,3,\ldots }$
• ${\displaystyle \sum _{n=0}^{\infty }n^{2}z^{n}={\frac {z(1+z)}{(1-z)^{3}}}}$     (generating function of the sequence of square numbers ) ${\displaystyle 0,1,4,9,\ldots }$
• ${\displaystyle \sum _{n=0}^{\infty }a^{n}z^{n}={\frac {1}{1-az}}}$     (generating function of the geometric sequence ) ${\displaystyle 1,a,a^{2},a^{3},\ldots }$
• ${\displaystyle \sum _{n=0}^{\infty }{c \choose n}z^{n}=(1+z)^{c}}$
• ${\displaystyle \sum _{n=0}^{\infty }{c+n-1 \choose n}z^{n}={\frac {1}{(1-z)^{c}}}}$
• ${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{n}}z^{n}=\ln {\frac {1}{1-z}}}$
• ${\displaystyle \sum _{n=0}^{\infty }{\frac {1}{n!}}z^{n}=e^{z}}$

Manipulation of generating functions

If a sequence is represented as a generating function, certain manipulations of the sequence correspond to corresponding manipulations of the generating function.

Let us consider e.g. B. the sequence with the generating function . Derive results ${\displaystyle 1,1,1,\ldots }$ ${\displaystyle \sum _{n=0}^{\infty }z^{n}={\frac {1}{1-z}}=F(z)}$

${\displaystyle F'(z)={\frac {1}{(1-z)^{2}}}=\sum _{n=0}^{\infty }(n+1)z^{n}}$.

This corresponds to the sequence multiplication with results ${\displaystyle 1,2,3,\ldots }$ ${\displaystyle z}$

${\displaystyle zF'(z)={\frac {z}{(1-z)^{2}}}=\sum _{n=0}^{\infty }nz^{n}}$.

So we get the sequence ${\displaystyle 0,1,2,3,\ldots }$

Deriving a generating function therefore corresponds to the multiplication of the nth member of the sequence with and subsequent index shift to the left, multiplication with z corresponds to a shift of the indices to the right. ${\displaystyle n}$

Let us consider another sequence with the generating function . If you multiply by the generating function from above according to the Cauchy product formula you get: ${\displaystyle a_{0},a_{1},a_{2},\ldots }$ ${\displaystyle \sum _{n=0}^{\infty }a_{n}z^{n}=G(z)}$ ${\displaystyle G(z)}$ ${\displaystyle F(z)}$

${\displaystyle G(z)F(z)=G(z){\frac {1}{1-z}}=(\sum _{n=0}^{\infty }a_{n}z^{n})(\sum _{n=0}^{\infty }1z^{n})=\sum _{n=0}^{\infty }(\sum _{k=0}^{n}a_{k}\ 1)z^{n}}$

So the nth coefficient of the product is of the form . That is exactly the partial sum of the first coefficients of the original generating function. The multiplication of a generating function with thus provides the partial sums. ${\displaystyle \sum _{k=0}^{n}a_{k}}$ ${\displaystyle n}$ ${\displaystyle {\frac {1}{1-z}}}$

The following table provides an overview of other possible manipulations:

episode	generating function
${\displaystyle (a_{n}+b_{n})_{n\geq 0}}$	${\displaystyle A(z)+B(z)}$
${\displaystyle (\sum _{k=0}^{n}a_{k}b_{n-k})_{n\geq 0}}$	${\displaystyle A(z)B(z)}$
${\displaystyle (\sum _{k=0}^{n}a_{k})_{n\geq 0}}$	${\displaystyle {\frac {1}{1-z}}A(z)}$
${\displaystyle (\lambda ^{n}a_{n})_{n\geq 0}}$	${\displaystyle A(\lambda z)}$
${\displaystyle ((n+1)a_{n+1})_{n\geq 0}}$	${\displaystyle A'(z)}$
${\displaystyle (na_{n})_{n\geq 0}}$	${\displaystyle zA'(z)}$
${\displaystyle (n^{2}a_{n})_{n\geq 0}}$	${\displaystyle zA'(z)+z^{2}A''(z)}$
${\displaystyle a_{0},0,a_{2},0,a_{4},0,\ldots }$	${\displaystyle {\frac {1}{2}}{\bigl (}A(z)+A(-z){\bigr )}}$
${\displaystyle 0,a_{1},0,a_{3},0,a_{5},\ldots }$	${\displaystyle {\frac {1}{2}}{\bigl (}A(z)-A(-z){\bigr )}}$

${\displaystyle A(z)}$is the generating function of the sequence , that of the sequence . ${\displaystyle a_{0},a_{1},a_{2},\ldots =(a_{n})_{n\geq 0}}$ ${\displaystyle B(z)}$ ${\displaystyle (b_{n})_{n\geq 0}}$

application

Generating functions are an important tool for solving recursions and difference equations as well as for counting number partitions . The pointwise multiplication of a generating function to the identity corresponding to the displacement of the modeled terms of the sequence by one position to the rear, front, as a new member having the index a is added. Assuming we have to solve the recursion , then it is , and it applies to the generating function ${\displaystyle z\mapsto z}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle f(n)=2\cdot f(n-1),f(0)=1}$ ${\displaystyle f(n)\cdot z^{n}=2z\cdot f(n-1)z^{n-1}}$

${\displaystyle F(z):=\sum _{n=0}^{\infty }f(n)\cdot z^{n}=f(0)+\sum _{n=1}^{\infty }f(n)\cdot z^{n}=1+2z\cdot \sum _{n=1}^{\infty }f(n-1)\cdot z^{n-1}=1+2z\cdot \sum _{n=0}^{\infty }f(n)\cdot z^{n}}$

so

${\displaystyle F(z)=1+2z\cdot F(z)}$

Solving for F yields

${\displaystyle F(z)={\frac {1}{1-2z}}.}$

But we know from the previous section that this corresponds to the series , so it is true after the coefficient comparison . ${\displaystyle \sum _{n=0}^{\infty }2^{n}z^{n}}$ ${\displaystyle f(n)=2^{n}}$

Different types of generating functions

There are other types of generating functions besides the usual generating function. Sometimes it proves convenient to consider sequences using the following two types of generating functions.

Exponential generating function

The exponentially generating function (or generating function of the exponential type ) of a sequence is the number . ${\displaystyle a_{n}}$ ${\displaystyle z\mapsto \sum _{n=0}^{\infty }{\frac {a_{n}}{n!}}z^{n}}$

For example, the exponential function is the exponentially generating function of the sequence ${\displaystyle e^{z}}$ ${\displaystyle 1,1,1,\ldots }$

Dirichlet generating function

The Dirichlet-generating function of a sequence is the series . It is named after Peter Gustav Lejeune Dirichlet . ${\displaystyle a_{n}}$ ${\displaystyle s\mapsto \sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}}$

For example, the Riemann zeta function is the Dirichlet generating function of the sequence ${\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}}$ ${\displaystyle 1,1,1,\ldots }$

Probability generating function

→ Main article : Probability generating function

If all are between zero and one and add up to one, then the generating function of this series is also called the probability generating function . She plays z. B. a role in the calculation of expected values and variances as well as in the addition of independent random variables . ${\displaystyle (a_{i})_{i\in \mathbb {N} }}$

Generating functions and the Z-transformation

Let be the ordinary generating function of and be the unilateral Z-transformation of . The relationship between the generating function and the Z-transform is ${\displaystyle G\{a_{n}\}(z)}$ ${\displaystyle (a_{n})}$ ${\displaystyle {\mathcal {Z}}\{a_{n}\}(z)}$ ${\displaystyle (a_{n})}$

${\displaystyle G\{a_{n}\}(z)={\mathcal {Z}}\{a_{n}\}{\Big (}{\frac {1}{z}}{\Big )}.}$

The corresponding generating functions can be obtained from a table of Z-transformations and vice versa.

Example: It is thus results ${\displaystyle {\mathcal {Z}}\{1\}(z)={\frac {z}{z-1}}.}$

${\displaystyle G\{1\}(z)={\frac {1/z}{1/z-1}}={\frac {z}{z}}\left({\frac {1/z}{1/z-1}}\right)={\frac {1}{1-z}}.}$

literature

Wikibooks: Linear recurrences, power series and their generating functions  - learning and teaching materials

• Martin Aigner : Discrete Mathematics . 5th, revised and expanded edition. Vieweg, Wiesbaden 2004, ISBN 3-528-47268-5 .
• Herbert S. Wilf: Generating Functionology. 3. Edition. AK Peters Ltd., Wellesley MA 2005, ISBN 978-1-56881-279-3 (2nd edition. Academic Press, Boston MA et al. 1994, ISBN 0-12-751956-4 , in PDF 1.18 MB ).