Explizite Formeln für Folgen

Nachdem wir in den vorigen Blog-Folgen (siehe hier und hier) den Identitätssatz für Potenzreihen kennengelernt und uns mit der Partialbruchzerlegung vetraut gemacht haben, sind wir nun soweit, dass wir für rekursiv definierte Folgen eine explizite Formel herleiten können.

Schema zur Herleitung

Bei der Herleitung gehen wir dabei nach einem festen Schema vor, das aus den folgenden vier Schritten besteht.

Zu einer rekursiv definierten Folge $(a_n)_{n\in\N_0}$ stellen wir die Potenzreihe $\sum_{n=0}^\infty a_n z^n$ auf und zeigen, dass die Potenzreihe einen Konvergenzradius $> 0$ hat. Damit stellt die Potenzreihe im Konvergenzgebiet eine Funktion dar, die wir üblicherweise mit $G(z)$ bezeichnen.
Durch die Anwendung der rekursiven Definition von $a_n$ auf die Potenzreihe ermitteln wir eine explizite Darstellung der Funktion $G(z)$.
Wir führen eine Partialbruchzerlegung für $G(z)$ durch und stellen die Funktion $G(z)$ als Linearkombination bekannter Potenzreihen dar.
Wir fassen die Linearkombination der Potenzreihen zu einer Potenzreihe zusammen. Mit dem Identitätssatz folgt dann, dass die Koeffizienten dieser Potenzreihe identisch zu den Folgengliedern $a_n$ sein müssen. So entsteht die explizite Formel für die $a_n$.

Für den Leser, der die Technik der sogenannten erzeugenden Funktion noch nicht kennt, dürfte dies recht abstrakt klingen. Deshalb schauen wir uns ein ausführliches Beispiel an, in dem ich die vier Schritte genau erkläre.

Für das Beispiel betrachten wir die rekursiv definierte Folge $(a_n)$ mit \[ a_0 = 0, a_1 = 4, a_n = 2a_{n-1} + 3a_{n-2} \text{ für } n \geq 2. \] Die ersten Folgenglieder dieser Folge sind \[ 0,4,8,28,80,244,728,2188,\ldots \] Eine einfache explizite Formel für die $a_n$ ist zunächst nicht erkennbar.

Schritt 1

Wir stellen die Potenzreihe \[ \sum_{n=0}^\infty a_n z^n \] auf und zeigen, dass diese Potenzreihe einen Konvergenzradius $R > 0$ hat.

Mit Induktion können wir leicht zeigen, dass die Folgenglieder $a_n$ alle nicht negativ sind: Per Definition gilt $a_0, a_1 \geq 0$, womit der Induktionsanfang gelegt ist. Die Induktionsvoraussetzung besagt, dass alle $a_k$ mit $k\leq n-1$ nicht negativ sind. Damit folgt dann, dass auch $2 a_{n-1} + 3 a_{n-2} =a_n$ nicht negativ ist.

Also gilt $a_n \geq 0$ für alle $n\in \N_0$. Damit folgt nun \[ a_n = 2 a_{n-1} + 3 a_{n-2} \geq 2 a_{n-1} \geq a_{n-1}. \] Also ist die Folge monoton wachsend.

Das Quotienkriterium liefert nun \[ \left| \frac{a_{n+1}z^{n+1}}{a_n z^n}\right| = \frac{2a_n + 3a_{n-1}}{a_n}|z| \leq \frac{2a_n + 3a_n}{a_n} |z| = 5|z|. \] Für die Abschätzung haben wir im Zähler $3a_{n-1}$ durch $3a_n$ ersetzt. Weil die Folge monoton wachsend ist, ist diese Abschätzung korrekt.

Aus der Anwendung des Quotientenkriteriums folgt, dass die Reihe für alle $|z| < \frac{1}{5}$ konvergiert, der Konvergenzradius $R$ also mindestens $\frac{1}{5}$ beträgt.

Beachte, dass wir den Konvergenzradius $R$ nicht exakt bestimmt haben. Dies müssen wir aber auch nicht. Es genügt zu zeigen, dass $R > 0$ gilt, was uns gelungen ist. Damit stellt die Potenzreihe $\sum_{n=0}^\infty a_n z^n$ auf der Menge $D = \{z\in \C \mid |z| < \frac{1}{5} \}$ eine Funktion \[ \begin{array}{ccccl} G(z) & : & D & \rightarrow & \C \\ & & z & \mapsto & \sum_{n=0}^\infty a_n z^n \end{array} \] dar. Diese Funktion $G(z)$ wird auch die erzeugende Funktion der Folge $(a_n)$ genannt.

Schritt 2

Wir ermitteln eine explizite Darstellung der erzeugenden Funktion $G(z)$. Hierfür stellen wir zunächst $G(z)$ mithilfe der Potenzreihendarstellung als Term in $G(z)$ selbst dar. \begin{eqnarray*} G(z) = \sum_{n=0}^\infty a_n z^n & = & 0 + 4z + \sum_{n=2}^\infty a_n z^n \\ & = & 4z + \sum_{n=2}^\infty (2a_{n-1} + 3a_{n-2})z^n \\ & = & 4z + 2\sum_{n=2}^\infty a_{n-1} z^n + 3\sum_{n=2}^\infty a_{n-2}z^n \\ & = & 4z + 2z\sum_{n=2}^\infty a_{n-1} z^{n-1} + 3z^2 \sum_{n=2}^\infty a_{n-2}z^{n-2} \\ & = & 4z + 2z\sum_{n=1}^\infty a_{n-1} z^{n-1} + 3z^2 \sum_{n=2}^\infty a_{n-2}z^{n-2} \\ & = & 4z + 2z\sum_{n=0}^\infty a_n z^n + 3z^2 \sum_{n=0}^\infty a_n z^n \\ & = & 4z + 2zG(z) + 3z^2G(z) \end{eqnarray*}

Zur Herleitung: Wir ziehen zuerst die ersten beiden Summanden aus der Potenzreihe heraus, weil die rekursive Definition für $a_n$ nur für $n\geq 2$ anwendbar ist. Dann wenden wir die rekursive Definition an und spalten anschließend die Potenzreihe in zwei Potenzreihen auf. Aus der linken Potenzreihe klammern wir $2z$ aus, aus der rechten $3z^2$. Nun nehmen wir in der linken Potenzreihe zusätzlich den Summanden für $n=1$ auf. Da $a_0 = a_{1-1} = 0$ gilt, machen wir damit nichts falsch. Die vorletzte Zeile entsteht dann durch Indexverschiebungen. Die beiden Potenzreihen stellen nun wieder die erzeugende Funktion $G(z)$ dar.

Damit haben wir eine Gleichung in $G(z)$, die wir leicht nach $G(z)$ auflösen können. \begin{eqnarray*} & & G(z) = 4z +2zG(z) + 3z^2 G(z) \\ & \Rightarrow & G(z) - 2zG(z) - 3z^2 G(z) = 4z \\ & \Rightarrow & G(z) (1 -2z -3z^2) = 4z \\ & \Rightarrow & G(z) = \frac{4z}{1 -2z -3z^2} \end{eqnarray*} Damit haben wir nun eine explizite Darstellung der erzeugenden Funktion $G(z)$. Es gilt: \[ G(z) = \frac{4z}{1 -2z -3z^2}. \]

Schritt 3

In der aktuellen Darstellung können wir $G(z)$ nicht als Linearkombination von Potenzreihen darstellen. Wir führen daher eine Partialbruchzerlegung durch. Zunächst gilt (bei Erweiterung um $-\frac{1}{3}$): \[ G(z) = \frac{4z}{1 -2z -3z^2} = \frac{-\frac{4}{3}z}{z^2 + \frac{2}{3}z - \frac{1}{3}}. \] Die $p$-$q$-Formel liefert uns \[ z_{1,2} = -\frac{1}{3} \pm \sqrt{\frac{1}{9} + \frac{1}{3}} = -\frac{1}{3} \pm \sqrt{\frac{4}{9}} = -\frac{1}{3} \pm \frac{2}{3} = \frac{1}{3} \text{ bzw. } -1 \] als Nullstellen des Nennerpolynoms. Also existieren Zahlen $A,B\in\R$ mit \[ \frac{-\frac{4}{3}z}{z^2 + \frac{2}{3}z - \frac{1}{3}} = \frac{A}{z -\frac{1}{3}} + \frac{B}{z+1}. \] Wir ermitteln die Zahlen $A,B$: \begin{eqnarray*} \frac{-\frac{4}{3}z}{z^2 + \frac{2}{3}z - \frac{1}{3}} & = & \frac{A}{z -\frac{1}{3}} + \frac{B}{z+1} \\ & = & \frac{A(z+1)+B(z-\frac{1}{3})}{(z-\frac{1}{3})(z+1)} \\ & = & \frac{(A+B)z + (A-\frac{1}{3}B)}{z^2 + \frac{2}{3}z - \frac{1}{3}}. \end{eqnarray*} Ein Koeffizientenvergleich liefert das lineare Gleichungssystem \[ \begin{array}{rcrcr} A & + & B & = & -\frac{4}{3} \\ A & - & \frac{1}{3}B & = & 0 \end{array} \] mit der Lösung $A=-\frac{1}{3}$ und $B=-1$. Damit gilt \begin{eqnarray*} G(z) = \frac{4z}{1 -2z -3z^2} & = & \frac{-\frac{1}{3}}{z-\frac{1}{3}} - \frac{1}{z+1} \\ & = & \frac{1}{1-3z} - \frac{1}{1+z}. \end{eqnarray*} Nun gilt, dass beide Terme von $G(z)$ als geometrische Reihen dargestellt werden können: \[ \frac{1}{1-3z} = \sum_{n=0}^\infty (3z)^n = \sum_{n=0}^\infty 3^n z^n \] und \[ \frac{1}{1+z} = \frac{1}{1 - (-z)} = \sum_{n=0}^\infty (-z)^n = \sum_{n=0}^\infty (-1)^n z^n. \] Damit haben wir eine Darstellung von $G(z)$ als Linearkombination bekannter Potenzreihen.

Schritt 4

Aus Schritt 3 folgt \begin{eqnarray*} \sum_{n=0}^\infty a_n z^n = G(z) & = & \frac{1}{1-3z} - \frac{1}{1+z} \\ & = & \sum_{n=0}^\infty 3^n z^n - \sum_{n=0}^\infty (-1)^n z^n \\ & = & \sum_{n=0}^\infty (3^n - (-1)^n) z^n. \end{eqnarray*} Also haben wir zwei Potenzreihen, die die gleiche Funktion darstellen. Mit dem Identitätssatz für Potenzreihen folgt \[ a_n = 3^n - (-1)^n. \] Damit haben wir die gewünschte explizite Formel für die Folgenglieder $a_n$ der rekursiv definierten Folge.

Vorige Folge Nächste Folge