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\ge 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}^{\mathrm{\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}^{\mathrm{\infty }}{a}_{n+1}{z}^{n+1}=3\sum _{n=0}^{\mathrm{\infty }}{a}_n{z}^{n+1}+\sum _{n=0}^{\mathrm{\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}^{\mathrm{\infty }}{a}_n{z}^n=\sum _{n=0}^{\mathrm{\infty }}n{z}^n=z+2z^2+3z^3+\mathrm{...}=z\cdot (1+2z+3z^2+\mathrm{...})=z\cdot (\sum _{n=0}^{\mathrm{\infty }}{z}^n{)}^{\prime }=z\cdot (\frac{1}{1-z}{)}^{\prime }=\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}^{\mathrm{\infty }}(3z{)}^n+\frac{1}{3}\cdot \sum _{n=0}^{\mathrm{\infty }}n\cdot (3z{)}^n=\sum _{n=0}^{\mathrm{\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

• im Informatik-Forum SS08 Beispiel 254

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