# 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 Ax = 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 nun diese Matrizen und lösen das Gleichungssystem:

    def polySum(i,k):
        return sum(lambda j:j^k, 1,i)

    def sumSolve(k):
        A = Matrix.fromFunction(k+1,k+1, lambda i,j: i^j, 1)
        b = Vector.fromFunction(k+1, lambda i: polySum(i,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