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)\ast \frac{(1-2x{)}^2}{2x}=1$

$(a_0+a_1\ast x+a_2\ast x^2+\mathrm{...})\ast \frac{(1-2x{)}^2}{2x}=a_0+x(-4a_0+a_1)+x^2(4a_0-4a_1+a_2)+\mathrm{...}$

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 $\to a_n=n\ast 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)