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

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$

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag von Neverlasting

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}=3a_{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}=3zA(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 }nz^{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}+n3^{n-1})$

Wähle C = a0:

$a_{n}=3^{n}C+n3^{n-1}$

Links

• im Informatik-Forum SS08 Beispiel 254

• TU Wien:Mathematik 2 UE (diverse)/Übungen SS08/Beispiel 225