3. Summen höherer Potenzen
Bisher haben wir unsere Formeln durch geometrische Überlegungen gewonnen. Die lassen sich aber nicht anschaulich auf höhere Dimensionen übertragen. Für die geometrische Darstellung der Summe von vierten Potenzen müssten wir zum Beispiel eine Reihe von wachsenden Hyperwürfeln im fünfdimensionalen Raum stapeln.
Unsere bisherigen Erkenntnisse sind:
- Die Summe der ersten
nnatürlichen Zahlen ist ein Polynom vom Grad 2. - Die Summe der ersten
nQuadratzahlen ist ein Polynom vom Grad 3. - Die Summe der ersten
nKubikzahlen ist ein Polynom vom Grad 4.
Was liegt also näher als die Vermutung:
Die Summe k-ter Potenzen ist ein Polynom vom Grad k+1
Dass die folgende Gleichung richtig ist, sehen Sie, wenn Sie den inneren (nicht grün unterlegten) Bereich spaltenweise betrachten: In jeder Spalte heben sich die beiden Terme auf!
\begin{matrix}
\green{n^3 = n^3}
& -(n-1)^3 & & & & & & \cr
& +(n-1)^3 & -(n-2)^3 & & & & & \cr
& & +(n-2)^3 & -(n-3)^3 & & & & \cr
& & & +\ldots\quad & & & & \cr
& & & & +3^3 & -2^3 & & \cr
& & & & & +2^3 & -1^3 & \cr
& & & & & & +1^3 & \green{-0^3}
\end{matrix}
Durch zeilenweises Aufsummieren (von unten nach oben) ergibt sich damit:
\begin{aligned}
n^3 & = \sum_{i=1}^n \pink{(i^3 - (i-1)^3)} = \sum_{i=1}^n(3i^2-3i+1) \cr
& = 3 \sum_{i=1}^n{i^2} - 3 \sum_{i=1}^n i + n
\end{aligned}
Damit erhalten wir:
\sum_{i=1}^n{i^2} = \frac{n^3}3 + \sum_{i=1}^n i - \frac n 3
Wir haben hier zwar nur festgestellt, was wir schon wissen: Die Summe der Quadratzahlen muss ein Polynom vom Grad 3 sein.
Die Überlegung lässt sich aber ganz einfach (zu einem
Induktionsbeweis) verallgemeinern:
Wenn wir die Gleichung statt für n^3 für n^k schreiben,
wird der rötlich unterlegte Term zu \pink{(i^k-(i-1)^k)}.
Beim Ausmultiplizieren von (i-1)^k kommt die Potenz i^k genau einmal vor.
In der Differenz bleiben also nur noch Potenzen bis k-1, deren Summen nach Induktionsvoraussetzung
Polynome vom Grad k sind.
Bestimmung der Polynomkoeffizienten
Nachdem wir nun wissen, dass die Summe der Quadratzahlen ein kubisches Polynom von n sein muss, machen wir den Ansatz
\sum_{i=1}^n{i^2} = a_0 + a_1 n + a_2 n^2 + a_3 n^3
Wie können wir die Koeffizienten a_0 bis a_3 bestimmen?
Wenn wir n = 0 einsetzen, ergibt sich
\sum_{i=1}^0{i^2} = a_0
und damit a_0 = 0, weil die leere Summe den Wert Null hat!
Es liegt nahe, drei weitere Spezialfälle heranzuziehen, um die verbleibenden Unbekannten
a_1 bis a_3 zu bestimmen.
Wir probieren es mit n = 1, 2, und 3:
\begin{aligned}
\sum_{i=1}^1{i^2} & = \ocher{1^2} & = a_0 + \green 1\; a_1 + \green{1^2}\; a_2 + \green{1^3}\; a_3 \cr
\sum_{i=1}^2{i^2} & = \ocher{1^2 + 2^2} & = a_0 + \green 2\; a_1 + \green{2^2}\; a_2 + \green{2^3}\; a_3 \cr
\sum_{i=1}^3{i^2} & = \ocher{1^2 + 2^2 + 3^2} & = a_0 + \green 3\; a_1 + \green{3^2}\; a_2 + \green{3^3}\; a_3
\end{aligned}
Damit ergibt sich das Gleichungssystem
\begin{aligned}
\green 1\; a_1 & + & \green 1\; a_2 & + & \green 1\; a_3 & = \ocher 1 \cr
\green 2\; a_1 & + & \green 4\; a_2 & + & \green 8\; a_3 & = \ocher 5 \cr
\green 3\; a_1 & + & \green 9\; a_2 & + & \green{27}\; a_3 & = \ocher{14}
\end{aligned}
Die Lösung des Gleichungssystems delegieren wir an mathGUIde:
Dazu packen wir die farbig unterlegten Zahlen in zwei „Kisten“ (Matrizen – dazu mehr an anderer Stelle!) und lassen uns die unbekannten Polynomkoeffizienten a_1, a_2, a_3 in einer dritten Kiste (Matrix) zurückliefern:
A = \green{\begin{pmatrix}
1 & 1 & 1 \cr
2 & 4 & 8 \cr
3 & 9 & 27\end{pmatrix}},
\quad\textbf b = \ocher{\begin{pmatrix}
1 \cr
5 \cr
14\end{pmatrix}}
Die drei ausgegebenen Zahlen sind die gesuchten Werte a_1, a_2, a_3.
Damit ergibt sich:
\sum_{i=1}^n{i^2} = \frac 1 6 n + \frac 1 2 n^2 + \frac 1 3 n^3
Bitte überzeugen Sie sich, dass das mit der über den Pyramidentrick gefundenen Formel übereinstimmt!
Verallgemeinerung
Das Prinzip dieses Beispiels verallgemeinern wir jetzt, um für beliebige natürliche Exponenten k die Koeffizienten des Polynoms der Summenformel zu gewinnen.
\sum_{i=1}^n{i^k}
Wir wissen, dass die Summe der k-ten Potenzen ein Polynom
vom Grad k+1, mit a_0 = 0 ist:
\sum_{i=1}^n{i^k} = a_1 n + a_2 n^2 + \ldots + a_{k+1} n^{k+1}
Um die unbekannten Koeffizienten zu bestimmen, setzen wir die Zahlen 1, 2, \ldots, k+1 ein:
\begin{aligned}
\green{1^1} a_1 & + \green{1^2} a_2 + & \ldots & + \green{1^{k+1}} a_{k+1} & = \ocher{\displaystyle{\sum_{i=1}^1{i^k}}} \cr
\green{2^1} a_1 & + \green{2^2} a_2 + & \ldots & + \green{2^{k+1}} a_{k+1} & = \ocher{\displaystyle{\sum_{i=1}^2{i^k}}} \cr
\cdots & \cr
\green{(k+1)}a_1 & + \green{(k+1)^2} a_2 & + \ldots & + \green{(k+1)^{k+1}} a_{k+1} & = \ocher{\displaystyle{\sum_{i=1}^{k+1}{i^k}}}
\end{aligned}
Dieses Gleichungssystem lässt sich schreiben als A \textbf x = \textbf b mit:
A = \green{\begin{pmatrix}1^1 & 1^2 & \ldots & 1^{k+1} \cr
2^1 & 2^2 & \ldots & 2^{k+1} \cr
\cdots & \cr
(k+1)^1 & (k+1)^2 & \ldots & (k+1)^{k+1} \end{pmatrix}}
\textbf x = \begin{pmatrix}a_1 \cr a_2 \cr \vdots \cr a_{k+1}\end{pmatrix}
\quad
\textbf b = \ocher{\begin{pmatrix}\sum_{i=1}^1{i^k} \cr \sum_{i=1}^2{i^k} \cr \vdots \cr \sum_{i=1}^{k+1}{i^k}\end{pmatrix}}
Wir definieren nun diese Matrizen und lösen das Gleichungssystem, wobei wir auf die JavaScript-üblichen 0- statt 1-basierten Indizes achten müssen:
Das zweite Ergebnis bedeutet:
\sum_{i=1}^n{i^5} = -\frac 1 {12}n^2 + \frac 5 {12}n^4 + \frac 1 2 n^5 + \frac 1 6 n^6
Den erhaltenen Spaltenvektor der Koeffizienten wandeln wir in einen Array um und bilden daraus ein Polynom (Klasse Poly). Dabei fügen wir den nicht berücksichtigten konstanten Koeffizienten (0) wieder ein:
Weiter zu: Astronomische Getriebe und Kettenbrüche
