# Summen von natürlichen Zahlen

1. Die ersten hundert natürlichen Zahlen
2. Summen von Quadrat- und Kubikzahlen
3. Summen höherer Potenzen

## 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 Erkennnisse sind:

- Die Summe der ersten n natürlichen Zahlen ist ein Polynom vom Grad 2.
- Die Summe der ersten n Quadratzahlen ist ein Polynom vom Grad 3.
- Die Summe der ersten n Kubikzahlen 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 grün unterlegten Bereich spaltenweise betrachten: In jeder Spalte heben sich die beiden Terme auf!

\def\green{\bbox[#d0ffd0,2pt]} \matrix{ \matrix{n^3 = n^3 \cr \quad \cr \quad \cr \quad \cr \quad \cr \quad \cr \quad} \green{\matrix{ - (n-1)^3 & & & & & & \cr + (n-1)^3 & {}- (n-2)^3 & & & & & \cr & {}+ (n-2)^3 & {}- (n-3)^3 & & & & \cr & & {}+ \ldots \quad\quad & & & & \cr & & & {}+3^3 & {}-2^3 & \cr & & & & {}+2^3 & {}-1^3 \cr & & & & & {}+1^3 \cr }} \matrix{\quad \cr \quad \cr \quad \cr \quad \cr \quad \cr \quad \cr {}-0^3}}
Durch zeilenweises Aufsummieren (von unten nach oben) ergibt sich damit:
\def\pink{\bbox[#ffe0e0,2pt]} \eqalign{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 }
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 n3 für nk schreiben, wird der rötlich unterlegte Term zu (ik - (i-1)k). Beim Ausmultplizieren von (i-1)k kommt die Potenz ik 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 a0 bis a0 bestimmen?
Wenn wir n = 0 einsetzen, ergibt sich
\sum_{i=1}^0{i^2} = a_0
und damit a0 = 0, weil die leere Summe den Wert Null hat!

Es liegt nahe, drei weitere Spezialfälle heranzuziehen, um die verbleibenden Unbekannten a1 bis a3 zu bestimmen. Wir probieren es mit n = 1, 2, und 3:

\def\green{\bbox[#d0ffd0,2pt]} \def\ocher{\bbox[#ffe0a0,2pt]} \eqalign{\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 \cr }
Damit ergibt sich das Gleichungssystem
\def\green{\bbox[#d0ffd0,2pt]} \def\ocher{\bbox[#ffe0a0,2pt]} \eqalign{\green1 a_1 & + & \green1 a_2 & + & \green1 a_3 & = \ocher 1 \cr \green2 a_1 & + & \green4 a_2 & + & \green8 a_3 & = \ocher 5 \cr \green3 a_1 & + & \green9 a_2 & + & \green{27} a_3 & = \ocher{14} }
Die Lösung des Gleichungssystems delegieren wir an mathGUIde:
Zunächst packen wir die farbig unterlegten Zahlen in eine Matrix und einen Spaltenvektor:
\def\green{\bbox[#d0ffd0,2pt]} \def\ocher{\bbox[#ffe0a0,2pt]} A = \green{\pmatrix{1 & 1 & 1 \cr 2 & 4 & 8 \cr 3 & 9 & 27}}, \quad \textbf b = \ocher{\pmatrix{1 \cr 5 \cr 14}}

    A = Matrix.fromString("1,1,1; 2,4,8; 3,9,27")
    b = Matrix.fromString("1; 5; 14")

Jetzt lassen wir uns die unbekannten Polynomkoefizienten geben:

    A.solve(b)

Die drei ausgegebenen Zahlen sind die gesuchten Werte a1, a2, a3. 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!

### Übungsaufgabe

Schreiben Sie ein mathGUIde-Programm, das für beliebige natürliche k die Koeffizienten des Polynoms der Summenformel

\sum_{i=1}^n{i^k}
berechnet.

Zur Lösung.