TU Wien:Analysis 2 UE (diverse)/Übungen SS19/Beispiel 245

From VoWi
Jump to navigation Jump to search

Lösen sie die Rekursion aus Beispiel 225) mit Hilfe von erzeugenden Funktionen:

 a_n = 3a_{n-1} + 3^{n-1}  (n \geq 1), a_0 = 2

Lösungsvorschlag von Neverlasting[edit]

Das Verfahren läuft sehr ähnlich wie das Beispiel im Buch zur erzeugenden Funktion. Ich hab es auch zuerst mit Partialbruchzerlegung versucht, aber da wir ja (1-3z)^2 im Nenner haben, nützt sie uns leider wenig. Hier meine Lösung (Prof. Winkler hat sie gefallen :)):

a_{n+1} = 3 a_n + 3^n

A(z) = \sum_{n=0}^\infty a_n z^n

Wir wollen die Gleichung auf diese Form bringen. Multipliziere sie deshalb mit z^(n+1) und summiere über alle n:

\sum_{n=0}^\infty a_{n+1} z^{n+1} = 3 \sum_{n=0}^\infty a_n z^{n+1} + \sum_{n=0}^\infty z^{n+1} 3^n

Benutze nun die Definition von A(z):

A(z) - a_0 = 3z A(z) + \frac{z}{1-3z}

Umformen, sodass wir auf eine Gleichung für A(z) kommen:

A(z) = \frac{a_0}{1-3z} + \frac{z}{(1-3z)^2}

Nun verwende folgendes Lemma: Betrachte die arithmetische Reihe (0, 1, 2, ...) mit der Gleichung a_n = n und stelle dafür eine erzeugende Funktion B(z) auf: B(z) = \sum_{n=0}^\infty a_n z^n = \sum_{n=0}^\infty n z^n = z + 2z^2 + 3z^3 + ... = z \cdot (1 + 2z + 3z^2 + ...) = z \cdot (\sum_{n=0}^\infty z^n)' = z \cdot (\frac{1}{1-z})' = \frac{z}{(1-z)^2}

A(z) = \frac{a_0}{1-3z} + \frac{z}{(1-3z)^2} = \frac{a_0}{1-3z} + \frac{1}{3} \cdot \frac{3z}{(1-3z)^2}

Nun wende B(z) an sowie die Formel für die geometrische Reihe.

A(z) = a_0 \cdot \sum_{n=0}^\infty (3z)^n + \frac{1}{3} \cdot \sum_{n=0}^\infty n \cdot (3z)^n = \sum_{n=0}^\infty z^n \cdot (3^n a_0 + n 3^{n-1})

Wähle C = a0:

a_n = 3^n C + n 3^{n-1}

Links[edit]

  • im Informatik-Forum SS08 Beispiel 254