Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen/ Potenzreihen-Identitäten

Die einfachste Potenzreihe ist die geometrische Reihe:

$1+x+x^{2}+x^{3}+x^{4}+\cdots =\sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}$.

Sie erzeugt den konstanten Wert 1. Durch Differentiation und anschließende Multiplikation mit x (man spricht auch von der Anwendung des xD-Operators) erhalten wir jene Funktion, die die Folge a_n=n, also die natürlichen Zahlen erzeugt.

$0+x+2x^{2}+3x^{3}+4x^{4}+\cdots =\sum _{n=0}^{\infty }nx^{n}={\frac {x}{(1-x)^{2}}}$.

Jede weitere Anwendung des xD-Operators erzeugt die nächste Potenz von n.

$0+x+4x^{2}+9x^{3}+16x^{4}+\cdots =\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {x(x+1)}{(1-x)^{3}}}$.

$\sum _{n=0}^{\infty }n^{3}x^{n}={\frac {x(x^{2}+4x+1)}{(1-x)^{4}}}$.

$\sum _{n=0}^{\infty }n^{4}x^{n}={\frac {x(x+1)(x^{2}+10x+1)}{(1-x)^{5}}}$.

$\sum _{n=0}^{\infty }n^{m}x^{n}=(xD)^{m}{\frac {1}{(1-x)}}$.    (P1)

Hier bezeichnet (xD)^m die m-malige Anwendung des xD-Operators.

Geht es darum, Potenzen einer konstanten Zahl c zu erzeugen, genügt es, x in der geometrischen Reihe durch cx zu ersetzen:

$1+cx+c^{2}x^{2}+c^{3}x^{3}+c^{4}x^{4}+\cdots =\sum _{n=0}^{\infty }c^{n}x^{n}={\frac {1}{1-cx}}$.

Ebenso gelten die Regeln des xD-Operators für diese Funktion, und wir erhalten

$\sum _{n=0}^{\infty }c^{n}n^{m}x^{n}=(xD)^{m}{\frac {1}{(1-cx)}}$.    (P2)

Wir werden sehen, dass alle linearen Rekurrenzen bzw. ihre rationalen erzeugenden Funktionen Zahlenfolgen erzeugen, die sich als Summe von den in (P1) und (P2) erzeugten Ausdrücken darstellen lassen. Die Behandlung weiterer Identitäten von Potenzreihen ist hier daher gar nicht notwendig.