Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen/ Die Partialsummen der Kubikzahlen

Ein häufig auftretendes Problem sind Partialsummen-Folgen und Differenzen-Folgen, die sich aus vorgegebenen Zahlenfolgen ableiten. Als Operation auf Potenzreihen betrachtet, erhält man die erste Differenz durch Multiplikation der Erzeugenden mit (1-x):

${\begin{aligned}A(x)&=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+a_{4}x^{4}+\cdots \\(1-x)A(x)&=a_{0}+(a_{1}-a_{0})x+(a_{2}-a_{1})x^{2}+(a_{3}-a_{2})x^{3}+(a_{4}-a_{3})x^{4}+\cdots \end{aligned}}$

Daraus folgt unmittelbar, dass die Funktion A(x)/(1-x) die erste Partialsumme der Folge a_n erzeugt:

${\frac {A(x)}{1-x}}=\sum _{n\geq 0}\left(\,\sum _{k=0}^{n}a_{k}\right)x^{n}$.

Wir wollen dies am Beispiel der Kubikzahlen 0, 1, 8, 27, 64, 125... veranschaulichen. Die Partialsummenfolge der Kubikzahlen

$a_{n}=\sum _{k=0}^{n}k^{3}=\{0,1,9,36,100,225\ldots \}$

besitzt die erzeugende Funktion (siehe das Kapitel über Potenzreihen-Identitäten)

$A(x)=\sum _{n\geq 0}a_{n}x^{n}={\frac {1}{1-x}}\cdot {\frac {x(x^{2}+4x+1)}{(1-x)^{4}}}={\frac {x(x^{2}+4x+1)}{(1-x)^{5}}}$.

Die Nullstelle des Nennerpolynoms hat den Wert 1 und ist fünffach, das heißt, in der geschlossenen Form von a_n können Potenzen von n bis n⁴ auftreten. Der Ansatz für die Partialbruchzerlegung von A(x) lautet

${\frac {x(x^{2}+4x+1)}{(1-x)^{5}}}={\frac {A}{1-x}}+{\frac {Bx}{(1-x)^{2}}}+{\frac {Cx(x+1)}{(1-x)^{3}}}+{\frac {Dx(x^{2}+4x+1)}{(1-x)^{4}}}+{\frac {Ex(x+1)(x^{2}+10x+1)}{(1-x)^{5}}}$,

${\begin{aligned}x^{3}+4x^{2}+x=&A(1-x)^{4}+B(-x^{4}+3x^{3}-3x^{2}+x)+C(x^{4}-x^{3}-x^{2}+x)\\&+D(-x^{4}-3x^{3}+3x^{2}+x)+E(x^{4}+11x^{3}+11x^{2}+x)\end{aligned}}$

mit dem Gleichungssystem

${\begin{aligned}0&=A\\1&=-4A+B+C+D+E\\4&=6A-3B-C+3D+11E\\1&=-4A+3B-C-3D+11E\\0&=A-B+C-D+E\end{aligned}}$

Es hat die Lösung C=1/4, D=1/2, E=1/4 und daher ist

$a_{n}=\sum _{k=0}^{n}k^{3}={\frac {1}{4}}n^{2}+{\frac {1}{2}}n^{3}+{\frac {1}{4}}n^{4}={\frac {n^{2}(n+1)^{2}}{4}}$.

Was auch gleich dem Quadrat der Dreieckszahlen ist. Diese Identität läßt sich selbstverständlich auch auf anderem Weg (und in diesem Fall vielleicht sogar schneller) beweisen. Es ging in diesem Kapitel jedoch um die Demonstration der allgemeinen Methode zur Behandlung von Partialsummen, und um mehrfache Nullstellen bei der Partialbruchzerlegung.