Erzeugendenfunktionen

Für lineare und nicht lineare Rekursionsgleichungen erhält man oft eine Lösung, indem man die f_n als Koeffizienten einer Potenzreihe betrachtet und eine geschlossene Form, der dadurch definierte Funktion sucht.

Definition: Für eine Folge $(f_n)_{n\geq 0}$ ist die ``erzeugende Funktion`` definiert als:

$$\text{F}(z)=\sum_{n=0}^{\infty}\text{f}_n z^n;\quad z \in \mathbbm{C}$$

Exponentielle Erzeugendenfunktion:

$$\text{F}(z)= \sum_{n\geq 0}\frac{\text{f}_n}{n!}z^n$$

auch Notation:

$$\text{F}(z)=\sum\limits_{n\gt}\text{f}_nz^n \Rightarrow \text{f}_n=[z^n]\text{F}(z)$$

Sei $\text{F}(z)=\sum\limits_{n\gt}\text{f}_nz^n$ und $\text{G}(z)=\sum\limits_{n\geq 0}\text{g}_nz^n$

Erz. Fkt. n-tes Folgenglied Anmerkungen:

$$c\text{F} c\text{f}_n$$

$$\text{F}+\text{G} \text{f}_n+\text{g}_n$$

$$\text{F} \cdot \text{G} \text{h}_n:=\sum\limits_{i=0}^{n}\text{f}_{i}\text{g}_{n-i} \left(\sum\limits_{n\geq 0}\text{f}_nz^n\right) \left(\sum\limits_{n\geq 0} \text{g}_nz^n\right)=\sum\limits_{n\geq 0}\text{h}_nz^n$$

$$\text{h}_n=\sum\limits_{i=0}^{n}\text{f}_{i}\text{g}_{n-i}$$

$$z^k\text{F} \text{\underline{if} } n < k \text{ \underline{then} } 0 \text{\underline{else} } \text{f}_{n-k} \text{ \underline{fi} }$$

$$\frac{\text{F}(z)}{1-z} \sum\limits_{i=0}^{n}\text{f}_i \frac{1}{1-z} = \sum\limits_{n \geq 0} z^n$$

$$z\frac{d\text{F}(z)}{dz} n\text{f}_n$$

$$\int\limits_0^x\text{F}(t)dt \text{\underline{if} } n = 0 \text{ \underline{then} } 0 \text{ \underline{else} } \frac{\text{f}_{n-1}}{n} \text{ \underline{fi}} \text{f}_nz^n \text{f}_n\frac{z^{n+1}}{n+1}$$

$$\text{F}(cz) c^n\text{f}_n \text{F}(cz) = \sum\limits_{n \geq 0} \text{f}_n(cz)^n = \sum\limits_{n \geq 0}\text{f}_nc^nz^n$$

Beispiel:

$$\begin{split} \text{F}(z) :=& \sum_{n\geq 0}2^nz^n = \frac{... ...1-2z)} = \sum_{n\geq 0}\sum_{i=0}^n(n-i)2^{i}z^{n}\end{split}$$

Partialbruchzerlegung:

$$\begin{split} \frac{z}{(1-z)^2(1-2z)} &= \overbrace{\frac{-... ...geq 0}nz^n - \underbrace{2\sum_{n\geq 0}z^n}_{(1)};\end{split}$$

Also:

$$\begin{split} \sum_{i=0}^{n}2^i(n-i) &= [z^n](\text{FG})(z)... ...\geq 0}(2^{n+1}-n-2)z^n\right) \\ &= 2^{n+1}-n-2;\end{split}$$