Benutzer:Reziprok/GenerierendenfunktionBeispiel

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoßen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Reziprok auf.

Der Lösungsweg stammt von mir. Ich habe ihn absichtlich so ausführlich wie nur möglich gestaltet. Trotzdem kann ich Fehler nicht ausschließen und bin für Korrekturen und Verbesserungsvorschläge dankbar. (Bitte über die Diskussionsseite) Ich habe diese Lösung anfangs in einem Forum gepostet, deswegen bedarf sie einiger Überarbeitung. Sobald sie fertig ist, werde ich sie als Beispiel zum Erzeugende Funktion Artikel hinzufügen.--Reziprok 00:42, 27. Nov. 2006 (CET)

Gegeben ist folgende Rekurrenz:

$T(0)=0$

$T(1)=3$

$T(n)=T(n-1)+2n$

Gesucht ist eine geschl. Form.

Lösung:

1. Folge definieren:

$n<0:g_{n}=0$

$n\geq 0:g_{n}=g_{n-1}+2n+[n=1]$

2. mit $z^{n}$ multiplizieren und aufsummieren.

$\sum _{n\geq 0}g_{n}z^{n}=G(z)=zG(z)+\underbrace {2\sum _{n\geq 0}nz^{n}} _{={\frac {2z}{(1-z)^{2}}}}+z$

EDIT: Auf Nachfrage hier noch der genaue Rechenweg für die Summe

$2\sum _{n\geq 0}nz^{n}=2\sum _{n\geq 0}{n \choose 1}z^{n}=2\sum _{n\geq -1}{1+n \choose 1}z^{n+1}=2z{\Big (}{\Big (}\sum _{n\geq 0}{1+n \choose 1}+{0 \choose 1}{\Big )}z^{n}{\Big )}=2z\sum _{n\geq 0}{1+n \choose 1}z^{n}={\frac {2z}{(1-z)^{2}}}$

Die Summe habe ich m.H. dieser Formel umgeformt:

$\sum _{n=0}^{\infty }{m+n \choose m}a^{n}z^{n}={\frac {1}{(1-az)^{m+1}}}$

3. umstellen:

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

4. wieder in Potzenreihen:

$G(z)=z\sum _{n\geq 0}z^{n}+2z\sum _{n\geq 0}{n+2 \choose 2}z^{n}=\sum _{n\geq 0}z^{n+1}+2\sum _{n\geq 0}{\frac {(n+1)(n+2)}{2}}z^{n+1}=\sum _{n>0}z^{n}+\sum _{n>0}n(n+1)z^{n}$

$\Rightarrow g_{n}=1+n(n+1)~fuer~(n>0)$