# Summen von natürlichen Zahlen

## Lösung der Ü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.

Wir wissen, dass die Summe der k-ten Potenzen ein Polynom vom Grad k+1, mit a0 = 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, ..., k+1 ein:

\eqalign{1^1 a_1 & + 1^2 a_2 + & \ldots & + 1^{k+1} a_{k+1} & = \sum_{i=1}^1{i^k}\cr 2^1 a_1 & + 2^2 a_2 + & \ldots & + 2^{k+1} a_{k+1} & = \sum_{i=1}^2{i^k} \cr \cdots & \cr (k+1)a_1 & + (k+1)^2 a_2 & + \ldots & + (k+1)^{k+1} a_{k+1} & = \sum_{i=1}^{k+1}{i^k} \cr }
Dieses Gleichungssystem lässt sich schreiben als A x = b mit:
A = \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} }
\textbf x = \pmatrix{a_1 \cr a_2 \cr \vdots \cr a_{k+1}} \quad \textbf b = \pmatrix{\sum_{i=1}^1{i^k} \cr \sum_{i=1}^2{i^k} \cr \vdots \cr \sum_{i=1}^{k+1}{i^k}}
Wir definieren diese Matrizen mit Hilfe von List Comprehensions und rechnen mit rationalen Zahlen:

    def sumSolve(k):
        # Berechnet die Koeffizienten des Polynoms für die Summe 1^k + 2^k + ... + n^k
        A = Matrix ([ [Rational(i^j) for j in fromTo(1, k+1)]
                      for i in fromTo(1, k+1) ])
        b = ~Vector([ sum( [Rational(j^k) for j in fromTo(1, i)] )
                      for i in fromTo(1, k+1) ])
        return A.solve(b)

Zur Probe: Die Koeffizienten für k=2 und für k=5

    sumSolve(2)
    sumSolve(5)

Das zweite Ergebnis besagt:

\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