Erzeugende Funktionen?
Hallo,
ich verstehe den folgenden Schritt nicht ganz:
Wie macht man das?
Warum folgt das?
Liebe Grüße
1 Antwort
Da fehlt zunächst der Startwert, die Rekursion ist nur für n>=1 angegeben, was ist a_0? Ich gehe mal von a_0=1 aus, das gibt die Rekursionsformel, wenn man n=0 einsetzt. Andernfalls musst du das folgende entsprechend anpassen.
Die erzeugende Funktion ist A(x) = Summe( n=0 bis unendlich ) a_n x^n.
Die Rekursion (und a_0) eingesetzt ergibt:
A(x) = 1 * x^0 + Summe( n=1 bis unendlich ) 1 * x^n + Summe( i=0 bis n ) (n-i) a_i x^n
Der Teil Summe( n=1 bis unendlich ) 1 * x^n ist klar, der Rest ist
1 + Summe( n=1 bis unendlich ) Summe( i=0 bis n ) (n-i) a_i x^n =
Summe( n=0 bis unendlich ) Summe( i=0 bis n ) (n-i) a_i x^n,
und das ist das Produkt der beiden erzeugenden Funktionen,
Summe( n=0 bis unendlich ) a_n x^n und
Summe( n=0 bis unendlich ) n x^n,
man sagt auch, es ist die Faltung. Wenn man diese beiden Reihen miteinander multipliziert, dann sammelt man für gegebenes n die jeweiligen Summanden, die zum gleichen Faktor x^n führen, das sind a_i x^i * (n-i) x^(n-i) für i von 0 bis n.
Dankeschön, hätte am Anfang schreiben sollen dass a0=0 ist…