Erzeugende Gleichung ( Generatingfunctionology )

Die Generatingfunctionologo entspricht einer elementaren Z-Transformation. Es gibt im Netz dazu kostenlos von H.Wilf
als PDF. http://www.math.upenn.edu/~wilf/DownldGF.html
Im Folgenden ist kurz die Funktionsweise anhand einiger einfacher Beispiele dargestellt :

Grundgedanke :
*************
Gesucht sei die analytische Loesung a(n)=f(n,a0) einer DZGL. Anstatt die Loesung als explizite Funktion anzugeben wird zunaechst versucht diese als Potenzreihe anzugeben.
A(n)= sum (a_n*x^n, n>0 .oo). Die Methode basiert somit auf einem Potenzreihenansatz.
A(n) ist eine Transformationsvariable wie F(z) in der Z-Transformation.
Dazu wird die DZGL auf beiden Seiten mit x^n multipliziert und im Interavll n_start..oo die Summe gebildet. Durch geschicktes Umformen der Summen wird versucht A(x) zu ermitteln.
Die Methode ist im Grunde eine Z-Transformation auf elementarem Weg.

Beispiel :
a(n+1)=2*a(n)+1 (a0=0, Loesung a(n)=2^n-1)

"GENERATING-TRANSFORMATION"
************************************
Linke Seite :

Sum( a(n+1)*x^n 0...) = a1*x^0+a2*x^1+a3*x^2 ...
Ziel ist es A(x)=sum(a_n*x^n zu erzeugen => verschieben der Indizes durch erweitern mit x/x =>
Sum( a(n+1)*x^n 0...) = a1*x^0+a2*x^1+a3*x^2 . =.(a1*x^1+a2*x^2+a3*x^3 ..) / x =
Hinzufuegen von a0
Sum( a(n+1)*x^n 0...) = (a0 a1*x^1+a2*x^2+a3*x^3 ... -x0)/x =(A(n)-x0)/x
da x0=0
A(n)/x (Dieses Ergebnis erhaelt man auch schneller mit den Regeln der Z Transformation)

Rechte Seite :

Sum( 2*a_n*x^n +x^n ...) = 2*A(x)+ Sum(x^n ... ) => geometrische Reihe fuer x<0
= 2*A(x)+ 1/(1-x)
Linke Seite = rechte Seite :
A(n)/x = 2*A(x)+ 1/(1-x) ....

x
--------------- = A(x)
(1-x) (1-2x)

Partialbruchzerlegung
x/(1-x)/(1-2x)=x* r_1 /(1-x) + r2_ /(1-2*x)
von Hand oder einfach mit MAPLE :

convert( 1/(1-x)/(1-2*x) ,parfrac,x);
****************************

A(x)=x* ( 2/(1-2*x) - 1/(1-x)
******************

"RUECKTRANSFORMATION"
***************************
Behandeln der Brueche als geometrische Reihen liefert fuer denen Koeffizienten nach etwas umrechnen :
a_n=2^n-1
------------------------------------------------------------------------------------------------------------

Beispiel 2 :

a(n+1)=2*a(n)+n (a0=1)

Loesungsskizze :
Linke Seite :
(A(n)-x0)/x =
Rechte Seite :
2*A(x)+ Sum(n*x^n ... )
Die Summe kann man durch Differentation auf eine geometrsiche Reihe zurueckfuehren. ...
.... A(x) = (1 - 2x + 2x^2) / (1 - x)^2/(1 - 2x)

convert((1 - 2*x + 2*x^2) / (1 - x)^2/(1 - 2*x),parfrac,x);

A(x) = 2/(1-2*x)-1/(1-x)^2
Der erste Summand liefert 2*2^n.
Zweiter Summand :
1/(1-x)^2 ist die Ableitung der geometrischen Reihe und liefert daher -(n+1) =>
A(x) = 2^(n+1)-n-1
.