TU Wien:Diskrete Mathematik für Informatik UE (Drmota)/Übungen WS10/Beispiel 18

Angabe

Erzeugende Funktionen

$A(x)={\frac {2x}{(1-2x)^{2}}}$, a(n) = ?

Lösung

a(n)=n*2^n

Ansatz: $A(x)*{\frac {(1-2x)^{2}}{2x}}=1$

$(a_{0}+a_{1}*x+a_{2}*x^{2}+...)*{\frac {(1-2x)^{2}}{2x}}=a_{0}+x(-4a_{0}+a_{1})+x^{2}(4a_{0}-4a_{1}+a_{2})+...$

Man setzt: $a_{0}=1$ und $a_{1}=2$ (Term 2 ergibt 0) und der rest muss auch in summe 0 ergeben -> Rekursion

$4a_{n}-4a_{n+1}+a_{n+2}=0$

Diese mit M2-Kenntnissen lösen $\rightarrow a_{n}=n*2^{n}$

Etwas umständlich, und eigentlich benutzt man erzeugende Funktionen um Rekursionen zu berechnen und nicht umgekehrt, hat wer eine einfachere Alternative?

--Anwesender 22:59, 18. Okt. 2010 (CEST)