Lösen der Rekursion $a_{n}=2a_{n-1}+(1+2^{n})^{2}$ Für $n\geq 1,a_{0}=2$

Hilfreiches[Bearbeiten | Quelltext bearbeiten]

$A(z)=\sum _{n=0}^{\infty }a_{n}z^{n},A(z)-a_{0}=\sum _{n\geq 1}^{\infty }a_{n}z^{n},A(z)=\sum _{n\geq 1}^{\infty }a_{n-1}z^{n-1}$

Geometrische Reihe $\sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}$

Lösungsvorschlag von madsonic[Bearbeiten | Quelltext bearbeiten]

Hab versucht möglichst alle Rechenschritte hinzuschreiben.

Leider geht die Probe nicht auf aber der Lösungsweg sollte prinzipiell richtig sein...wurde in der Übung so vergerechnet. In der Übung wurde auch darüber hinweggesehn das ein paar Umformungen mit Wolframalpha gemacht wurden. (weiter unten bei den Summenformeln). Vielleicht findet jemand ja mal den Rechenfehler und bessert ihn aus..

zuerst die Angabe mit $z^{n}$ multiplizieren: $a_{n}z^{n}=2a_{n-1}z^{n}+(1+2^{n})^{2}z^{n}$

dann Aufsummieren mit $\sum _{n\geq 1}^{\infty }$ , Der Lösungsweg wird einfacher wenn man anstatt $n=0$ $n\geq 1$ nimmt. Die Idee dazu stammt vom verlinkten Ähnlichen Beispiel.

$\sum _{n\geq 1}^{\infty }a_{n}z^{n}=2\sum _{n\geq 1}^{\infty }a_{n-1}z^{n}+\sum _{n\geq 1}^{\infty }(1+2^{n})^{2}z^{n}$

die Gleichung etwas umformen und das Quadrat ausquadrieren:

$\sum _{n\geq 1}^{\infty }a_{n}z^{n}=2z\sum _{n\geq 1}^{\infty }a_{n-1}z^{n-1}+\sum _{n\geq 1}^{\infty }(1+2^{n+1}+4^{n})z^{n}$

Summen Aufspalten:

$\sum _{n\geq 1}^{\infty }a_{n}z^{n}=2z\sum _{n\geq 1}^{\infty }a_{n-1}z^{n-1}+\sum _{n\geq 1}^{\infty }z^{n}+\sum _{n\geq 1}^{\infty }2^{n+1}z^{n}+\sum _{n\geq 1}^{\infty }4^{n}z^{n}$

Einsetzen der Erzeugenden Funktion $A(z)$ , $a_{0}$ ist ja laut angabe 2:

$A(z)-2=2zA(z)+\sum _{n\geq 1}^{\infty }z^{n}+\sum _{n\geq 1}^{\infty }2^{n+1}z^{n}+\sum _{n\geq 1}^{\infty }2^{2n}z^{n}$

Nebenrechnungen Geometrische Reihe [1]:

$\sum _{n\geq 1}^{\infty }z^{n}=\sum _{n=0}^{\infty }z^{n}-z^{0}={\frac {1}{1-z}}-1={\frac {z}{1-z}}$
$\sum _{n\geq 1}^{\infty }2^{n+1}z^{n}=2\sum _{n=0}^{\infty }2^{n}z^{n}-z^{0}=2\sum _{n=0}^{\infty }(2z)^{n}-1={\frac {4z}{1-2z}}$
$\sum _{n\geq 1}^{\infty }4^{n}z^{n}=\sum _{n=0}^{\infty }4^{n}z^{n}-z^{0}=\sum _{n=0}^{\infty }(4z)^{n}-1={\frac {4z}{1-4z}}$

$A(z)$ auf eine Seite bringen, herausheben: $A(z)(1-2z)-2={\frac {z}{1-z}}+{\frac {4z}{1-2z}}+{\frac {4z}{1-4z}}$ Dividieren, 2 auf die andere Seite: $A(z)={\frac {z}{(1-z)(1-2z)}}+{\frac {4z}{(1-2z)^{2}}}+{\frac {4z}{(1-4z)(1-2z)}}+{\frac {2}{1-2z}}$ Die zwei Brüche mit Zähler 4z Zusammenfassen:

ACHTUNG die folgende Zeile ist falsch!!!

$A(z)={\frac {z}{(1-z)(1-2z)}}+{\frac {2-6z}{(1-2z)^{2}(1-4z)}}+{\frac {2}{1-2z}}$

Edit: Habe das Beispiel durchgerechnet und den Fehler entdeckt. Die letzte Zeile ist nicht richtig! Sollte eig so aussehen:

$A(z)={\frac {z}{(1-z)(1-2z)}}+{\frac {8z(1-3z)}{(1-2z)^{2}(1-4z)}}+{\frac {2}{1-2z}}$

So kommt man dann auf die richtige Lösung!

MfG Schurlinga

Partialbruchzerlegungen[Bearbeiten | Quelltext bearbeiten]

PBZ von ${\frac {z}{(1-z)(1-2z)}}={\frac {A}{1-z}}+{\frac {B}{1-2z}}={\frac {A(1-2z)+B(1-z)}{1-z)(1-2z)}}$ Wolframalpha:[2]

$z=A(1-2z)+B(1-z)$ ....für $z=1$ und $z={\frac {1}{2}}$ einsetzen ergibt $A=-1$ und $B=1$ und somit

 ${\frac {z}{(1-z)(1-2z)}}={\frac {-1}{1-z}}+{\frac {1}{1-2z}}$

PBZ von ${\frac {2-6z}{(1-2z)^{2}(1-4z)}}$ Wolframalpha:[3]

${\frac {2-6z}{(1-2z)^{2}(1-4z)}}={\frac {A}{1-4z}}+{\frac {B}{1-2z}}+{\frac {C}{(1-2z)^{2}}}$ $2-6z=A(1-2z)^{2}+B(1-4z)(1-2z)+C(1-4z)$ Einsetzen $z={\frac {1}{2}},z={\frac {1}{4}}$ ergibt C=1 und B=-1. Danach einsetzen für z=0 und man kommt auf B=-1. Ergebniss PBZ: ${\frac {2}{1-4z}}-{\frac {1}{1-2z}}+{\frac {1}{(1-2z)^{2}}}$

wieder zur Erzeugenden Funktion zurück[Bearbeiten | Quelltext bearbeiten]

Dann steht da: $A(z)={\frac {-1}{1-z}}+{\frac {1}{1-2z}}+{\frac {2}{1-4z}}-{\frac {1}{1-2z}}+{\frac {1}{(1-2z)^{2}}}+{\frac {2}{1-2z}}$ Vereinfachen : $A(z)={\frac {-1}{1-z}}+{\frac {2}{1-4z}}+{\frac {1}{(1-2z)^{2}}}+{\frac {2}{1-2z}}$ Wieder durch Geometrische Reihen ausdrücken: $A(z)=\sum _{n=0}^{\infty }-z^{n}+2\sum _{n=0}^{\infty }4^{n}z^{n}+\sum _{n=0}^{\infty }2^{n}(1+n)z^{n}+2\sum _{n=0}^{\infty }2^{n}z^{n}$ $z^{n}$ herausheben, summen umschreiben