Erzeugende Funktion

In verschiedenen Teilgebieten der Mathematik versteht man unter der erzeugenden Funktion (auch Generierendenfunktion genannt) einer Folge $a n$ die formale Potenzreihe

$\sum_{n=0}^{\infty} a_n z^n \ \ (:= GF(a_n)(z))$

Ein einfaches Beispiel ist die erzeugende Funktion der Folge $1,1,1,1,1,\ldots$ mit:

$GF(1)(z) = \sum_{n=0}^{\infty} z^n = \frac1{1-z},$

die Gleichheit gilt nur für $| z | < 1$ und folgt aus der Beobachtung

$(1-z) \cdot \sum_{n=0}^{\infty} z^n = 1.$

Durch die Verwendung formaler Potenzreihen spielen Konvergenzfragen keine Rolle - $z$ ist lediglich ein Symbol. Diese explizitere Darstellung der Potenzreihe ermöglich oft Rückschlüsse auf die Folge.

Inhaltsverzeichnis

1 Explizite Formeln für einige wichtige Potenzreihen
2 Anwendung
3 Verschiedene Typen von erzeugenden Funktionen
4 Siehe auch
5 Literatur

Explizite Formeln für einige wichtige Potenzreihen

Es gelten folgende Identitäten:

$\sum_{n=0}^{\infty} z^n = \frac{1}{(1-z)}$
$\sum_{n=0}^{\infty} n z^n = \frac{z}{(1-z)^2}$
$\sum_{n=0}^{\infty} n^2 z^n = \frac{z(1+z)}{(1-z)^3}$
$\sum_{n=0}^{\infty} a^n z^n = \frac{1}{1 - az}$
$\sum_{n=0}^{\infty} {c \choose n} z^n = (1 + z)^c$
$\sum_{n=0}^{\infty} {c + n - 1 \choose n} a^n z^n = \frac{1}{(1-az)^c}$
$\sum_{n=1}^{\infty} \frac{1}{n}z^n = \ln \frac{1}{1-z}$
$\sum_{n=0}^{\infty} \frac{1}{n!}z^n = e^z$

Anwendung

Erzeugende Funktionen liefern ein wichtiges Hilfsmittel für das Lösen von Rekursionen und von Differenzengleichungen. Eine Indexverminderung innerhalb der Folge entspricht einer Multiplikation der erzeugenden Funktion mit $z$ . Angenommen also wir haben die Rekursion $f(n) = 2\cdot f(n-1), f(0) = 1$ zu lösen, dann ist $f(n)\cdot z^n = 2z\cdot f(n-1) z^{n-1}$ , und es gilt für die erzeugende Funktion $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}$ , also

$F(z) = 1+ 2z \cdot F(z)$

Auflösen nach F liefert

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

Wir wissen aber (s.o.), dass dies der Reihe $\sum_{n=0}^\infty 2^n z^n$ entspricht, also gilt $f (n) = 2 n$ nach Koeffizientenvergleich.

Verschiedene Typen von erzeugenden Funktionen

Es gibt neben der gewöhnlichen erzeugenden Funktion noch weitere Typen von erzeugenden Funktionen. Manchmal erweist es sich als zweckmäßig, Folgen über den folgenden zwei Arten von erzeugenden Funktionen zu betrachten.

Exponentielle erzeugende Funktion

Die exponentiell erzeugenden Funktion (oder auch Erzeugenden Funktion vom Exponentialtyp) über einer Folge $a n$ ist die Reihe $\sum_{n=0}^\infty \frac{a_n}{n!} z^n$ . Wir bezeichnen die exponentiell erzeugende Funktion zur Folge $a n$ mit $E G F (a n)(z)$ .

Dirichlet erzeugende Funktion

Die Dirichlet erzeugende Funktion über einer Folge $a n$ ist die Reihe $\sum_{n=1}^{\infty} \frac{a_n}{n^s}$ . Sie ist benannt nach dem deutschen Mathematiker Peter Gustav Lejeune Dirichlet und soll im folgenden als $D G F (a n)(z)$ geschrieben werden.

Beispiele

Die exponentiell erzeugende Funktion der Folge $1,1,1,\dots$ (also $E G F (1)(z)$ ) ist demnach $e z$ .
Die Dirichlet erzeugende Funktion der Folge $1,1,1,\dots$ ( $D G F (1)(z)$ ) ist $\sum_{n=1}^\infty \frac{1}{n^s}$ , also die Riemannsche Zetafunktion $ζ(s)$ .