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