Verschiedene Möglichkeiten, die Formel für die Summe aufeinanderfolgender m-ter Potenzen herzuleiten, werden aufgezeigt. Es wird nicht mehr als Schulmathematik vorausgesetzt.
Artikel, die sich im Verzeichnis /tmp befinden, sind nie fertig, sonst wären sie woanders. Auf sie wird deswegen auch nicht von der Homepage aus verwiesen. Dass sie trotzdem öffentlich lesbar sind, hat den Grund, dass ich manchmal mit anderen während der Abfassung darüber diskutieren möchte.
Speziell dieser Artikel enthält einen systematischen Fehler, den ich zwar kurzfristig flicken könnte, über dessen sinnvollste Behebung ich aber lieber erst nachdenken würde. Und zwar setzt ein Teil der Formeln voraus, dass jeweils n Summanden beginnend mit 0, also unter Ausschluss von n selbst, aufsummiert werden, während die übrigen Formeln bis n einschließlich funktionieren. Speziell die ersten Formeln für
Was also falsch ist: die Formeln am Anfang (die sich wie eben beschrieben berichtigen lassen), und möglicherweise die eine oder andere Formel unterwegs, die man besser nachrechnet statt glaubt. Was richtig ist: der eingeschlagene Weg: so gehts wirklich.
Alle Leser, die hierüber gestolpert sind, bitte ich um Entschuldigung. Ich hätte klarer darauf hinweisen müssen, dass der Artikel nicht nur insgesamt "in statu nascendi" ist (siehe den unvermittelten Schluss ohne Einhaltung der eingangs gegebenen Versprechen), sondern dass er darüberhinaus eindeutig Fehler enthält.
Es ist ganz leicht, die Formel für die Summe der ersten n natürlichen Zahlen oder der ersten n Quadrat- oder Kubikzahlen zu beweisen - aber nur, wenn man sie kennt. Wie aber findet man zu einer gegebenen natürlichen Zahl m die Formel für die Summe der ersten n m-ten Potenzen, die wir im folgenden mit Sm(n) bezeichnen wollen?
Ist das m fest gegeben, dann ist diese Aufgabe auch relativ leicht: wir geben im folgenden zwei Lösungswege dafür komplett an und deuten einen dritten kurz an. Will man aber eine einzige Formel für alle beliebigen m, dann wird es erheblich schwieriger, aber auch viel reizvoller, weil sich unerwartete Querverbindungen zu anderen mathematischen Fragestellungen auftun. In diesem Artikel werden, vielfach ohne Beweis, diese Querverbindungen dargestellt und dabei darauf geachtet, dass möglichst keine Vorkenntnisse erwartet werden, die man nicht auf der Schule vermittelt bekommt. Das Thema dieses Artikels findet man am besten abgehandelt im Buch "Concrete Mathematics" von Ronald L. Graham, Donald E. Knuth und Oren Patashnik, dort aber über mehrere Kapitel (und eine Übungsaufgabe) verteilt und auf mehr mathematischem Vorwissen aufbauend.
Sei also Sm(n) = 1m + 2m + ... + nm.
Stattdessen bei 0 zu starten hätte offensichtlich nichts geändert,
außer für m=0.
Die ersten Formeln für Sm sind:
S0(n) = n S1(n) = (1/2)n2 - (1/2)n = n(n - 1) / 2 S2(n) = (1/3)n3 - (1/2)n2 + (1/6)n = n(2n - 1)(n - 1) / 6 S3(n) = (1/4)n4 - (1/2)n3 + (1/4)n2 = n2(n - 1)2 / 4 S4(n) = (1/5)n5 - (1/2)n4 + (1/3)n3 - (1/30)n = n(2n - 1)(n - 1)(3n2 - 3n - 1) / 30 S5(n) = (1/6)n6 - (1/2)n5 + (5/12)n4 - (1/12)n2 = n2(n - 1)2(2n2 - 2n - 1) / 12 S6(n) = (1/7)n7 - (1/2)n6 + (1/2)n5 - (1/6)n3 + (1/42)n = n(2n - 1)(n - 1)(3n4 - 6n3 + 3n + 1) / 42 S7(n) = (1/8)n8 - (1/2)n7 + (7/12)n6 - (7/24)n4 + (1/12)n2 = n2(n - 1)2(3n4 - 6n3 - n2 + 4n + 2) / 24
Ein paar empirische Beobachtungen lassen sich machen: Sm ist ein Polynom (m+1)-ten Grades; der führende Koeffizient ist 1/(m+1), der nächste ist -1/2, der darauffolgende m/12, der nächste verschwindet, und danach wird es ein wenig unübersichtlicher. Dass diese Gesetzmäßigkeiten tatsächlich gelten, muss man natürlich erst noch zeigen; es genügt nicht, sie aus ein paar Beispielen zu erschließen.
Wissen wir bereits, dass Sm ein Polynom (m+1)-ten Grades ist - bis jetzt ahnen wir es erst, haben es aber noch nicht bewiesen -, dann brauchen wir nur noch seine m+2 Koeffizienten zu finden. Dazu genügt es, die Werte an m+2 Stellen, etwa 0, 1, ... m+1, von Hand auszurechnen; wir erhalten so m+2 lineare Gleichungen für die m+2 Unbekannten. Dass die Gleichungen voneinander linear unabhängig sind, sich also weder widersprechen noch aus einander herleitbar sind, gilt in solchen Fällen, wo ein Polynom höchstens (m+1)-ten Grades durch die Funktionswerte an m+2 Stützstellen gegeben ist, immer. Diese beiden Aussagen wollen wir jetzt als zwei Sätze beweisen.
Satz. Es seien x0, x1, ..., xm paarweise verschieden, und y0, y1, ..., ym beliebig. Dann gibt es genau ein Polynom f höchstens m-ten Grades, so dass f(xi)=yi für i=0, 1, ..., m.
Beweis. Wir zeigen zunächst, dass es höchstens ein solches Polynom gibt. Gäbe es nämlich zwei verschiedene solche Polynome, dann wäre die Differenz nicht das Nullpolynom, hätte aber mehr als m Nullstellen. Ein Polynom m-ten Grades hat aber höchstens m Nullstellen, wenn es nicht das Nullpolynom ist. Daher genügt es zu zeigen, dass es mindestens ein solches Polynom gibt.
Sei nun für i=0, 1, ..., m das Polynom gi definiert als das Produkt der linearen Polynome (x-xj)/(xi-xj) über alle j=0, 1, ..., m außer j=i. Die gi sind Polynome m-ten Grades und es gilt gi(xi)=1 sowie gi(xj)=0 für i ungleich j. Damit hat das Polynom höchstens m-ten Grades f = g0y0 + ... + gmym die geforderte Eigenschaft.
Satz. Ist f ein Polynom m-ten Grades, so ist F(n) = f(1)+f(2)...+f(n) ein Polynom (m+1)-ten Grades.
Beweis. Induktion nach dem Grad von f, wobei die Induktionsbasis trivial ist.
f habe also den Grad m und der Satz sei für kleineren Grad bereits nach Induktionsvoraussetzung erfüllt. Wir definieren ein Polynom g m-ten Grades durch
g(n) = (n + 1)m+1 - nm+1 = C(m+1,1)·nm + C(m+1,2)·nm-1 + ... + C(m+1,m)·n + C(m+1,m+1)
wobei C(n,k) für den Binominalkoeffizienten "n über k" steht. Für g können wir die gewünschte Summe bilden:
g(1) + g(2) + ... + g(n) =
= (2m+1 - 1m+1) + (3m+1 - 2m+1) + ... + (nm+1 - (n - 1)m+1) + ((n + 1)m+1 - nm+1) =
= (n + 1)m+1 - 1m+1 = (n + 1)m+1 - 1
f und g sind also beide vom Grad m, haben also nicht verschwindende Höchstkoeffizienten. Sei r deren Quotient, so dass f-rg von kleinerem Grad als m ist. Die Funktion f lässt sich also schreiben als (f-rg)+rg; dabei ist f-rg nach Induktionsvoraussetzung von 1 bis n summierbar als Polynom höchstens m-ten Grades in n und rg ist summierbar als Polynom genau (m+1)-ten Grades wie eben dargestellt.
Wir haben eben eine Art Differentiation und Integration durchgeführt, nur ohne Grenzübergang: Die eben definierte Funktion g ist in einem gewissen Sinne die "Ableitung" der (m+1)-ten Potenz. Weil diese "diskrete Ableitung" im Gegensatz zur "richtigen" aus einer einfachen Potenz nicht wieder eine einfache Potenz, sondern einen komplizierten Ausdruck mit Binominalkoeffizienten macht, ist der umgekehrte Vorgang der "diskreten Integration", also der Summation, nicht einfach. Man kann sich nun retten, indem man die Potenz so definiert, dass die Ableitungsregel genauso einfach wird wie in der Differentialrechnung; dann wird auch die Integration von Potenzen genau so einfach. Diese neue Art Potenzen schreiben wir zum Unterschied von den richtigen Potenzen mit einem unterstrichenen Exponenten.
Definition. Wir definieren xm durch
xm = x(x - 1)·...·(x-m+1) = x! / (x - m)!
Die "fallende" m-te Potenz hat auch m Faktoren, jedoch sind die nicht alle gleich der Basis, sondern nur der erste, während jeder weitere um 1 kleiner ist als der vorangehende. Man beachte, dass 1m = 0 für m>1. Die Zweckmäßigkeit dieser Definition zeigt der folgende Satz.
Satz. Es gilt für m>0:
(x+1)m - xm = mxm-1
und
1m + 2m + ... xm = (x+1)m+1 / (m + 1)
Beweis.
(x+1)m - xm =
= (x + 1)! / (x - m + 1)! - x! / (x - m)! =
= ((x + 1)! - (x - m + 1)·x!) / (x + 1 - m)! =
= ((x + 1)·x! - (x - m + 1)·x!) / (x + 1 - m)! =
= mx! / (x + 1 - m)! =
= mxm-1
Damit ist
(x+1)m+1 / (m + 1) - xm+1 / (m + 1) = xm
und wir erhalten
1m + 2m + ... xm =
= ((2m+1 - 1m+1) + (3m+1 - 2m+1) + ... + ((x+1)m+1 - xm+1)) / (m + 1) =
= ((x+1)m+1 - 1m+1) / (m + 1) =
= (x+1)m+1 / (m + 1)
Es gibt noch mehr Ähnlichkeiten zwischen den Potenzen und diesen fallenden Potenzen, zum Beispiel gilt der binomische Satz genau gleich für beide. Auch die "Differentiation" folgt, wie hier, ganz ähnlichen Regeln mit kleinen Abweichungen (zum Beispiel ist die Funktion, die gleich ihrer Ableitung ist, dann nicht ex, sondern 2x).
Mit diesen Hilfsmitteln können wir auch die Formeln für die Potenzsummen herleiten, was im folgenden am Beispiel von S5 gezeigt werden soll.
Zunächst schreiben wir die fallenden m-ten Potenzen als Polynome:
n2 = n2 - n
n3 = n3 - 3n2 + 2n
n4 = n4 - 6n3 + 11n2 - 6n
n5 = n5 - 10n4 + 35n3 - 50n2 + 24n
n6 = n6 - 15n5 + 85n4 - 225n3 + 274n2 - 120n
Damit können wir den Spieß umdrehen und die fünfte Potenz als "Polynom" unter Verwendung fallender Potenzen schreiben:
n5 - n5 = 10n4 - 35n3 + 50n2 - 24n
n5 - n5 - 10n4 = 25n3 - 60n2 + 36n
n5 - n5 - 10n4 - 25n3 = 15n2 - 14n
n5 - n5 - 10n4 - 25n3 - 15n2 = n
so dass
n5 = n5 + 10n4 + 25n3 + 15n2 + n1
Die Koeffizienten, die bei der Umwandlung gewöhnlicher und fallender Potenzen in einander vorkommen, sind übrigens gerade die Stirling'schen Zahlen erster und zweiter Art - was natürlich nur den zu interessieren braucht, der den Stirling'schen Zahlen schon anderswo begegnet ist. Jedenfalls können wir jetzt aufsummieren:
(1/6)n6 + 2n5 + (25/4)n4 + 5n3 + 1/2n2
(1/6)n6 - (1/2)n5 + (5/12)n4 - (1/12)n2
n2(n-1)2(2n2-2n-1)/12