Allgemeine Formel für Potenzsummen
Eckhard Sebastian Maass
1 + 2 + 3 + ... + n = n(n+1)/2
Soweit, so gut. Jetzt habe ich in der Formelsammlung auch Summen fuer
1^2 + 2^2, 1^3 + 2^3 und 1^4 + 2^4 gefunden. Gbit es eine ganz
allgemeine Formel (1^v + 2^v ...)? Und wie sieht der Beweis dafür aus,
wenn es so eine gibt?
CU,
SEcki
--
God is Dead. -- Nietzsche
Nietzsche is Dead. -- God
Nietzsche is God. -- The Dead
Christian Semrau
>
> Gbit es eine ganz allgemeine Formel (1^v + 2^v ...)?
> Und wie sieht der Beweis dafür aus, wenn es so eine gibt?
Es gibt eine allgemeine Formel.
Die Formel fuer jede Potenz ist stets ein Polynom, und dessen
Koeffizienten heissen Bernoulli-Zahlen.
Ein Artikel dazu ist
http://www.lrz-muenchen.de/~hr/tmp/bernoulli.html
Fuer weitere suche z.B. unter 'bernoulli zahlen' oder 'potenzsumme'.
Gruss,
Christian
--
Warum laeuft das Huhn ueber das Moebius-Band?
Um auf die andere Seite - aehm...
Hermann Kremer
>Hallo,
>
>1 + 2 + 3 + ... + n = n(n+1)/2
>
>Soweit, so gut. Jetzt habe ich in der Formelsammlung auch Summen fuer
>1^2 + 2^2, 1^3 + 2^3 und 1^4 + 2^4 gefunden. Gbit es eine ganz
>allgemeine Formel (1^v + 2^v ...)? Und wie sieht der Beweis dafür aus,
>wenn es so eine gibt?
Es gibt eine allgemeine Formel, die 1631 von Johann Faulhaber
entdeckt wurde:
SUM{k=1...n} k^p =
= SUM{k=1...p} [ p! / (k! * (p+1-k)! ] * |B_k| * n^(p+1-k) ,
wobei die B_k die Bernoulli'schen Zahlen sind:
B_0 = 1
B_1 = -1/2
B_2 = 1/6
B_4 = -1/30
B_6 = 1/42
B_8 = -1/30
B_10 = 5/66
B_12 = -691/2730
B_14 = 7/6
B_16 = -3617/510
usw. und
B_3 = B_5 = B_7 = ... = 0 .
Diese Formel kann man z.B. mit der Euler-MacLaurin'schen
Integrationsformel herleiten:
INTEGRAL{1...n} f(x)*dx =
= SUM{k=1...n} f(k) -
- [ f(n) + f(1) ]/2 - B_2*[ f'(n) - f'(1) ]/2! - B_4*[ f'''(n) -
'''(1) ]/4! - ...
mit f(x) = x, x^2, x^3 usw.
Grüße
Hermann
--
Eckhard Sebastian Maass
> Es gibt eine allgemeine Formel, die 1631 von Johann Faulhaber
> entdeckt wurde:
>
> SUM{k=1...n} k^p =
> = SUM{k=1...p} [ p! / (k! * (p+1-k)! ] * |B_k| * n^(p+1-k) ,
Hmmm, den [ ... ] - Teil verstehe ich nicht ganz. Die Summe ist ein
Polynom (n^(p+1-k)) mit Bernoulli-Zahlen (|B_k|) als Koeffizienten. Was
macht der eckige Teil denn dann noch dort?
> Diese Formel kann man z.B. mit der Euler-MacLaurin'schen
> Integrationsformel herleiten:
Die Formel von Faulhaber oder die Bernoulli-Zahlen? Meine Suche in
Google brachte nichts.
Hermann Kremer
>> Es gibt eine allgemeine Formel, die 1631 von Johann Faulhaber
>> entdeckt wurde:
>>
>> SUM{k=1...n} k^p =
>> = SUM{k=1...p} [ p! / (k! * (p+1-k)! ] * |B_k| * n^(p+1-k) ,
>
>Hmmm, den [ ... ] - Teil verstehe ich nicht ganz. Die Summe ist ein
>Polynom (n^(p+1-k)) mit Bernoulli-Zahlen (|B_k|) als Koeffizienten. Was
>macht der eckige Teil denn dann noch dort?
Hallo Eckard,
der Term p!/(k! * (p+1-k)!) ist gerade ("p über k")/(p + 1 - k) .
>> Diese Formel kann man z.B. mit der Euler-MacLaurin'schen
>> Integrationsformel herleiten:
>
>Die Formel von Faulhaber oder die Bernoulli-Zahlen? Meine Suche in
>Google brachte nichts.
Beides ...
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Faulhaber.html
http://www.geocities.com/Paris/Rue/1861/arithm10.html
http://bonez.dhs.org/mathworld/contents/FaulhabersFormula.html
http://www-cs-faculty.stanford.edu/~knuth/preprints.html --> P142 (TeX-Datei)
http://www.phy.uni-bayreuth.de/~btp304/cp/uebung2.html
Die Euler-MacLaurin-Integration sollte in jedem Buch / Skript über numerische
Integration (Quadratur) stehen ...
Grüße
Hermann
--
Franz Lemmermeyer
> Es gibt eine allgemeine Formel, die 1631 von Johann Faulhaber
> entdeckt wurde:
>
> SUM{k=1...n} k^p =
> = SUM{k=1...p} [ p! / (k! * (p+1-k)! ] * |B_k| * n^(p+1-k) ,
>
> wobei die B_k die Bernoulli'schen Zahlen sind:
Wenn Du Deinem ersten link mal folgst, wirst Du feststellen, dass
Faulhaber das nur fuer die ersten 25 oder so Exponenten getan hat;
dass er die allgemeine Formel gefunden hat, ist ein Geruecht. Uebrigens
kann man diese Formeln per Induktion beweisen und gleichzeitig
Rekursionsformeln fuer die B_n erhalten.
franz
Hermann Kremer
<7ad55552.01102...@posting.google.com>...
Johann Faulhaber hat die Summenformeln in seiner
Academia Algebrae, Darinnen die miraculosischen Inventiones zu
den höchsten Cossen weiters continuirt und profitiert werden.
Augspurg, bey Johann Ulrich Schönigs, 1631.
(Stanford U. Libraries Sigel: QA154.8 F3 1631a f MATH)
nicht als Polynome in n, sondern als Polynome in N(n) = n*(n+1)/2 bis zur 25.
Potenz ausgerechnet und bis zur 17. Potenz publiziert. Dafür hat er auch zusätzlich
die Polynome in N(n) in die Polynome in n umgerechnet und angegeben.
Wie nun Don Knuth in seinem Faulhaber-Paper (4. Link) meint, hätte er auch
mit den damaligen Mitteln die allgemeine Formel für die Polynome in N(n)
beweisen können, obwohl er den Beweis nicht publiziert hat. Die Umrechnung in
die Polynome in n ist dann allerdings eine höllische Arbeit - so ganz ohne
Computer ...
Die Herleitung mittels der Euler-MacLaurin'schen Quadraturformel scheint
übrigens 1834 von Carl Gustav Jacob Jacobi publiziert worden zu sein.
Gruß
Hermann
--
>
>franz
Heini Holtenbeen
>Hallo,
>1 + 2 + 3 + ... + n = n(n+1)/2
>Soweit, so gut. Jetzt habe ich in der Formelsammlung auch Summen fuer
>allgemeine Formel (1^v + 2^v ...)? Und wie sieht der Beweis dafür aus,
>wenn es so eine gibt?
Hallo Eckhard,
ein sehr schöner Beitrag zu diesem Thema:
http://numbers.computation.free.fr/Constants/Miscellaneous/bernoulli.html
Gruß
Heini
--
__________________________________________________________
News suchen, lesen, schreiben mit http://newsgroups.web.de
Boudewijn Moonen
[Mit Verzoegerung, also: Mailed and posted]
Fuer natuerliches p >= 0 sei
S_p(n) := 0^p + 1^p + 2^p + ... + (n-1)^p
mit der Vereinbarung
S_0(n) := n .
Es ist dann bekannt, dass S_p(n) ein Polynom in n vom Grade
p+1 ist. Dieses laesst sich auf mindestens drei Weisen
bestimmen, als da sind:
A) Die Standardweise, oder The Bernoulli Connection
B) Die elegante Weise, oder The Stirling Connection
C) Die singulaere Weise, oder The Euler Connection.
A) The Bernoulli Connection
===========================
Wir nehmen an, S_p(n) sei durch ein Polynom in n gegeben,
das wir mit S_p(x) bezeichnen, wo x eine Unbestimmte ist.
Der Differenzenoperator Delta operiert auf Polynomen f
durch
Delta f(x) := f(x+1) - f(x) .
Es ist dann S_p(x) eindeutig charakterisiert durch
(1) Delta S_p(x) = x^p
(2) S_p(0) = delta_p0 (Kronecker Delta) .
Differenzieren von (1) liefert wegen der Linearitaet
des Differenzoperators
Delta S_p'(x) = px^{p-1} = pS_{p-1}(x)
somit
Delta(S_p'(x) - pS_p(x)) = 0
und somit ist S_p'(x) - pS_p(x) eine Konstante, etwa b_p.
Das ergibt die folgende Rekursion fuer S_p:
S_0(x) = x ,
(3)
S_p(x) = int_0^x S_{p-1}(t) dt + b_p x .
Die Konstante b_p bestimmt sich aus der Bedingung Delta S_p(0)
= 0 fuer p > 0, also wegen Delta S_p(0) = S_p(1) - S_p(0)
und S_0(x) = x aus
(4) S_p(1) = delta_p0 (Kronecker Delta) .
Damit berechnet man muehelos die ersten Polynome; in jedem
Schritt muss nur zusaetzlich b_p berechnet werden, die
restlichen Koeffizienten von S_p ergeben sich aus denen
von S_{p-1} durch Integration:
S_0(x) = x
S_1(x) = 1/2 x^2 - 1/2 x
S_2(x) = 1/3 x^3 - 1/2 x^2 + 1/6 x
S_3(x) = 1/4 x^4 - 1/2 x^3 + 1/4 x^2
S_4(x) = 1/5 x^5 - 1/2 x^4 + 1/3 x^3 - 1/30 x
S_5(x) = 1/6 x^6 - 1/2 x^5 + 5/12 x^4 - 1/12 x^2
S_6(x) = 1/7 x^7 - 1/2 x^6 + 1/2 x^5 - 1/6 x^3 + 1/42 x
S_7(x) = 1/8 x^8 - 1/2 x^7 + 7/12 x^6 - 7/24 x^4 + 1/12 x^2
S_8(x) = 1/9 x^9 - 1/2 x^8 + 2/3 x^7 - 7/15 x^5 + 2/9 x^3
- 1/30 x
S_9(x) = 1/10 x^10 - 1/2 x^9 + 3/4 x^8 - 7/10 x^6 + 1/2 x^4
- 3/20 x^2
S_10(x) = 1/11 x^11 - 1/2 x^10 + 5/6 x^9 - x^7 + x^5
- 1/2 x^3 + 5/66 x
S_11(x) = 1/12 x^12 - 1/2 x^11 + 11/12 x^10 - 11/8 x^8 + 11/6 x^6
- 11/8 x^4 + 5/12 x^2
S_12(x) = 1/13 x^13 - 1/2 x^12 + x^11 - 11/6 x^9 + 22/7 x^7
- 33/10 x^5 + 5/3 x^3 - 691/2730x
In der Tat laesst sich die Rekursion leicht explizit machen. Wegen
(3) prueft man leicht nach, dass gilt
S_p(x) = (1/(p+1)) sum_{k=1}^{p+1} (p+1|k) b_{p+1-k} x^k
wobei die b_j wegen (4) die Rekursion
(5) b_0 := 0 , sum_{k=1}^{p+1} (p+1|k) b_{p+1-k} = 0
erfuellen. Hierbei bezeichne
(m|n) := m!/(n!(m-n)!)
den ueblichen Binomialkoeffizienten. Damit erkennt man die b_p
als die handelsueblichen Bernoullizahlen B_p, die gerade durch
die Rekursion (5) definiert sind. Damit erhaelt man die Schlussformel
(B*) S_p(x) = (1/(p+1)) sum_{k=1}^{p+1} (p+1|k) B_{p+1-k} x^k
Mit den Eigenschaften der Bernoullizahlen prueft man nach, dass
die S_p(x) tatsaechlich die Potenzsummen sind, d.h. (1) und (2)
erfuellen. Damit hat man als Zugabe
KOROLLAR Die Differenzgleichung Delta g = f hat fuer ein Polynom
f ein Polynom g zur Loesung, welches bis auf eine Konstante
eindeutig bestimmt ist.
Fuer die Bernoullizahlen gibt es uebrigens, wie wir gleich sehen werden,
die folgende explizite Formel:
B_p = sum_{k=0}^p (-1)^k k!/(k+1) {p|k}
(6)
= sum_{j,k=0}^p (-1)^j 1/(k+1) (k|j) j^p .
Dabei bezeichne {p|k} Stirlingzahlen zweiter Art, zu denen wir jetzt
kommen.
B) The Stirling Connection
==========================
Die etwas unuebersichtliche Formel (B*) kommt daher zustande, weil
die Summation und Differenzbildung die diskrete Analoga zur
Integration und Differentation sind und sich die Monome x^k
friedlich gegenueber den letzteren Operationen, aber widerborstig
gegenueber den ersteren verhalten.
Genauer gesagt: Ist f ein Polynom, so loest das unbestimmte Integral
g = int f(x) dx die Gleichung g' = f und ist eindeutig charakterisiert
durch
(7) int_a^b f(x) dx = g(b) - g(a)
fuer alle a, b.
Analog loest die unbestimmte Summation, geschrieben g = sum f(x) delta x
die Gleichung Delta g = f und ist eindeutig charakterisiert
durch
(8) sum_a^{b-1} f(x) delta x = g(b) - g(a) .
fuer alle a, b. Unser Problem ist die Summation von f(x) = x^p,
d.h. die Loesung der Gleichung Delta S_p(x) = x^p .
Nun ist die Differentiation eines Monomes leicht, damit auch die
Integration als Umkehrung der Differentiation, und damit auch die
Integration eines Polynoms, wenn man es als eine Linearkombination
von Monomen schreibt, wegen der Linearitaet der Integration.
Aber die Monome verhalten sich stoerrisch gegenueber der
Differenzbildung. Daher ist die Summation von Polynomen
schwer, wenn man die Monome als Basis nimmt. Die Idee ist
daher, eine Basis {p_k} der Polynome zu finden, die sich
gegenueber Differenzbildung, und damit gegenueber Summation,
so friedlich verhaelt wie die der Monome gegenueber Differentiation
und Integration. Gesucht ist also eine Folge von Polynomen
p_0 = 1, p_1, p_2, .... mit deg p_k = k und
(9) Delta p_k = k p_{k-1} . k = 1, 2, ...
Mit etwas Herumprobieren erschliesst sich das leicht; ich verrate
hier nur das Ergebnis:
(10) p_k(x) := FFP(x,k) := x(x-1)(x-2)...(x-k+1)
genannt die *fallenden faktoriellen Potenzen*. Schreibt man nun
ein Polynom f als Linearkombination in diesen fallenden faktoriellen
Potenzen
f(x) = sum_k a_p FFP(x,k) ,
so gelingt die Summation muehelos:
(11) sum_{j=0}^{n-1} f(j) = sum_k a_k/(k+1) FFP(n,k+1) .
Damit ist unser einziges Problem, die Potenz x^p nach fallenden
faktoriellen Potenzen zu entwickeln:
(12) x^p = sum_{k=0}^p s_{p,k} FFP(x,k) .
Multipliziert man mit x und frickelt ein wenig herum, erhaelt man fuer
die Koeffizienten die Rekursion
s_{0,0} = 1 , s_{p,0} = 0 fuer p > 0,
(13)
s_{p+1,k} = s_{p,k-1} + k s_{p,k}
und damit ein Schema, das wie folgt beginnt:
1
0 1
0 1 1
0 1 3 1
0 1 7 6 1
0 1 15 25 10 1
Spaetestens hier erkennt der Vorbelastete, dass s_{p,k} = {p|k}, die
Stirlingsche
Zahl zweiter Art zu p, k. Diese ist definiert als die Anzahl der
k-elementigen Teilmengen einer p-elementigen Menge, und es ist
leicht zu sehen, dass diese Zahlen in der Tat auch die Rekursion (13)
erfuellen, daher die Gleichheit.
Aber das ist natuerlich unbefriedigend, es sollte dann auch eine direkte
kombinatorische Interpretation der Gleichung
(14) x^p = sum_{k=0}^p {p|k} FFP(x,k)
geben, und die gibt's (Thx, Sam...) : Da links und rechts Polynome vom
Grad p stehen, genuegt es, diese Gleichheit fuer p+1 verschiedene
natuerliche Zahlen nachzuweisen. Wir machen das wie folgt sogar fuer
alle natuerlichen Zahlen: Sei X eine Menge mit x Elementen und P eine
Menge mit P Elementen. Dann steht links die Anzahl aller Abbildungen
P --> X. Und rechts steht die auch, saeuberlich getrennt nach
Abbildungen mit je k Bildern....
Jetzt kann man direkt die Potenzen gemaess (11) summieren und erhaelt
(S*) S_p(x) = sum_{k=0}^p {p|k}/(k+1) FFP(x,k+1) .
Voila. So einfach ist das.
Zum Ausklang vergleiche man (S*) mit (B*), genauer die linearen Glieder.
Das gibt die erste Formel in (6) . Bildet man die hoechste iterierte
Differenz von (14), erhaelt man die folgende explizite Formel fuer die
Stirlingzahlen
(15) {p|k} = sum_{j=0}^p (-1)^{k-j} (k|j) j^p
und damit die zweite Formel in (6) .
C) The Euler Connection
=======================
Die "Eulerzahlen" <p|k> sind definiert als die Anzahl der Permutationen
pi der Zahlen von 1 bis p, welche k "Anstiege" haben, d.h. Stellen
i < k mit pi(i) < pi(k). Es gilt dann die mysterioese Formel
(16) x^p = sum_k <p|k> (x+k|p) ,
bekannt als "Identitaet von Worpitzky". Ein Idiotenbeweis gelingt wie
oben mittels der Rekursion
<0|0> = 1 , <p|0> = 0 fuer p > 0
(17)
<p+1|k> = (k+1)<p|k> + (n-k)<p|k-1>
und hier waere es auch schoen, eine kombinatorische Interpretation zu
haben (what about it, Sam?) . Summiert man (16) auf, erhaelt man
(E*) S_p(x) = sum_k <p|k> (x+k+1|p+1) .
Wieder voila. Aber diesmal ist das eigentlich keine systematische
Herleitung, sondern beruht auf der singulaeren Identitaet (16).
Als Leckerle zum Schluss eine explizite Formel fuer die Eulerzahlen:
<p|k> = sum_{j=0}^k (-1)^j (p+1|j) (k-j+1)^p .
MfG
--
Boudewijn Moonen
Institut fuer Photogrammetrie der Universitaet Bonn
Nussallee 15
D-53115 Bonn
To do is to be. -- Descartes.
To be is to do. -- Sartre.
Shobedobedo. -- Sinatra.
Harald Schreiber
Potenzsummen
Ich geb´s ja zu - das ist mir armen Mathemimöschenalles viel zu
schwer, es wird auch nicht leichter durch die notwendigen Tricks, um
die Formeln überhaupt darstellen zukönnen. Es gibt allerdings auch für
Aninfinitesimalisten wie mich Möglichkeiten, um Formeln für summe(i^r)
über den Index i von 1 bis n zur natürlichen Potenz r sukzessive zu
berechnen, wenn man klein anfängt. Man kann dann zwar nicht durch
einfaches Einsetzen z.B. die Summe der ersten 12 zur zehnten Potenz
erhobenen Zahlen berechnen, aber weiß, wie dahin zukommen ist, ohne
Kenntnis exotischerer als der Binomialkoeffizienten-hab ich jetzt
hoffentlich richtig geschrieben.
Ich gehe hier von einer Reihe von Identitäten aus :
- Dabei steht für r über z : (r|z) -
1^r = (1+1)^r - (r|1)1 - (r|2)1^2-...............-(r|r-1)1^(r-1)- 1
2^r = (2+1)^r - (r|1)2 - (r|2)2^2-...............-(r|r-1)2^(r-1)- 1
.
.
i^r = (i+1)^r - (r|1)i - (r|2)i^2-..............-(r|r-1)i^(r-1)- 1
.
.
k^r = (k+1)^r - (r|1)k - (r|2)k^2 ...............-(r|r-1)k^(r-1)- 1
----------------------------------------------------------------------------
Summieren und Ausgleichen ergibt
1 + k = (k+1)^r - (r|1)summe(i^1) - (r|2)summe(i^2)-...
..-(r|r-1)summe(i^(r-1))
wobei der Index i in den Summen jeweils von 1 bis k läuft.
Jetzt schimmerts schon durch :
summe(i^(r-1)) = ((k+1)((k+1)^(r-1)-1) - summe((r|s)summe(i^s)))/r
Dabei läuft der Index s in der äußeren Summerechts von 1 bis r-2 und
der Index i
in der inneren Summe rechts von1 bis k.
Wenn ich das jetzt noch ein bisschen umschreibe, komme ich zu
summe(i^(r+1)) = ((n+1)((n+1)^(r+1)-1)
-summe((r+2|s)summe(i^s)))/(r+2)
Dabei läuft der Index s in der äußeren Summe rechts von1 bis r und der
Index i
in der inneren Summe rechts von 1 bis n.
Gruss, Harald