Erzeugende Funktionen

Definition

Sei $\left(a_{n}\right)_{n\in\mathbb{N}_{0}}$ eine Folge. Die formale Potenzreihe

$$A\left(x\right):=\sum_{n\geq0}a_{n}x^{n}$$

heißt erzeugende Funktion zur Folge $\left(a_{n}\right)$.

Rechenregeln

Sind $\left(a_{n}\right),\left(b_{n}\right)$ zwei Folgen mit entsprechenden Funktionen $A\left(x\right),B\left(x\right)$, dann:

Summe

$\left(c_{n}\right):=\left(a_{n}+b_{n}\right)$
Hat erzeugende Funktion $C\left(x\right)=\sum_{n\geq0}c_{n}x^{n}$ und wir schreiben $C\left(x\right)=A\left(x\right)+B\left(x\right)$

Produkt

$\left(c_{n}\right):=\left(\sum_{k=0}^{n}a_{k}b_{n-k}\right)$
Hat erzeugende Funktion $C\left(x\right)=\sum_{n\geq0}c_{n}x^{n}$ und wir schreiben $C\left(x\right)=A\left(x\right)B\left(x\right)$

• Erzeugende Funktionen lassen sich gliedweise Integrieren und Differenzieren, um so neue erzeugende Funktionen zu konstruieren.

Inverse

Sei $A\left(x\right)=\sum_{n\geq0}a_{n}x^{n}$ erzeugende Funktion zu $\left(a_{n}\right)$. Dann heißt die erzeugende Funktion $B\left(x\right)=\sum_{n\geq0}b_{n}x^{n}$ invers zu $A\left(x\right)$, falls $A\left(x\right)B\left(x\right)=1$

• Hier ist $1$ die erzeugende Funktion zur Folge $\left(1,0,0,\ldots\right)$
• Die erzeugende Funktion $A\left(x\right)=\sum_{n\geq0}a_{n}x^{n}$ hat eine inverse erzeugende Funktion (auch: $A\left(x\right)$ ist invertierbar) genau dann, wenn $a_{0}\neq0$

Wichtige Erzeugende Funktionen

• geometrische Reihe
  $\sum_{n\geq0}\left(\alpha x\right)^{n}=\frac{1}{1-\alpha x}$
• $\sum_{n\geq0}\left(n\right)x^{n}=\frac{x}{\left(1-x\right)^{2}}$
• $\sum_{n\geq0}\left(n+1\right)x^{n}=\frac{1}{\left(1-x\right)^{2}}$
• $\sum_{n\geq0}\left(\begin{array}{c} n+k\\ k\end{array}\right)x^{n}=\frac{1}{\left(1-x\right)^{k+1}}$
• $\sum_{n\geq0}n^{2}x^{n}=\frac{x\left(x+1\right)}{\left(1-x\right)^{3}}$
• $b_{n}=\sum_{k=0}^{n}a_{k}$ die Folgen zu den erzeugenden Funktionen $A\left(x\right),B\left(x\right)$
  $B\left(x\right)=\frac{A\left(x\right)}{1-x}$

Lösen von linearen Rekursionsgleichungen durch erzeugende Funktionen

Gegeben

ist eine lineare Rekursionsgleichung $k$-ter Ordnung

$${\scriptstyle a_{0}=b_{0},\ldots,a_{k-1}=b_{k-1}\quad a_{n}=\sum_{i=1}^{k}c_{i}a_{n-i}\ \left(n\geq k\right)}$$

Ansatz

(Siehe Algorithmus 1 auf der nächsten Seite) Hierbei ersetzt man $A\left(x\right)=\sum_{n\geq0}a_{n}x^{n}$ durch die Rekursionsdefinition. Dabei entstehen Terme die wieder nur ein $a_{n}$ mit verschobenen Summationsbereich enthalten. Hier kann man nun durch Umformung das ganze wieder in ein Polynom plus $A\left(x\right)$ bringen.

Koeffizienten Zusammenfassen

(aus letzter Gleichung) zu $d_{i}$

$$A\left(x\right) = \sum_{i=0}^{k-1}d_{i}x^{i}+A\left(x\right)\sum_{i=1}^{k}\left(c_{i}x^{i}\right)$$

$$= \frac{\sum_{i=0}^{k-1}d_{i}x^{i}}{1-\sum_{i=1}^{k}\left(c_{i}x^{i}\right)}$$

Faktorisieren des Nenners

(Bestimmen von $\alpha_{i}$ und $m_{i}$)

$$1-\sum_{i=1}^{k}\left(c_{i}x^{i}\right)=\prod_{i=1}^{r}\left(1-\alpha_{i}x\right)^{m_{i}}$$

Partialbruchbruchzerlegung

(Bestimmen von $g_{i}\left(x\right)$)
$A\left(x\right)=\sum_{i=1}^{r}\frac{g_{i}\left(x\right)}{\left(1-\alpha_{i}x\right)^{m_{i}}}$
$g_{i}\left(x\right)$ wird von $x$ unabhängig, wenn beim Faktorisieren des Nenners komplexe Lösungen zugelassen werden. Dies erleichtert die Anwendung des nächsten Punktes.

Erstellen von Erzeugenden Funktion

für $A\left(x\right)$

$${\scriptscriptstyle A\left(x\right)=\sum_{n\geq0}\left(\underbrac... ...ray}{c} m_{i}-1+n\\ n\end{array}\right)\alpha_{i}^{n}\right)}_{f}x^{n}\right)}$$

Koeffizientenvergleich

 
Wenn alle $g_{i}$ nicht von $x$ abhängig sind, so ist $f=a_{n}$, wenn nicht muss diese Formel noch etwas umgestellt werden. Hiermit wäre ein geschlossener Ausdruck für $a_{n}$ gefunden.