Die Gauß-Summe
Satz (Gauß-Summe)
Für alle natürlichen Zahlen n gilt:
∑k ≤ n k = n (n + 1)2 (wobei ∑k ≤ n k = 0 + 1 + 2 + … + n)
Beweis
Wir zeigen die Aussage durch vollständige Induktion nach n ≥ 0.
Induktionsanfang n = 0: Es gilt
∑k ≤ 0 k = 0 = 0 (0 + 1)/2.
Induktionsschritt von n nach n + 1:
Es gelte ∑k ≤ n k = n (n + 1)/2 (Induktionsvoraussetzung I.V.). Wir zeigen:
∑k ≤ n + 1 k = (n + 1)(n + 2)2.
Es gilt:
| ∑k ≤ n + 1 k | = n + 1 + ∑k ≤ n k |
| =I.V. n + 1 + n (n + 1)2 = (n + 1) (1 + n2) | |
| = (n + 1) (2 + n2) = (n + 1)(n + 2)2. |
Wichtige Aspekte eines induktiven Beweises
Es ist alleine schon aus Gründen der Lesbarkeit wichtig, die Struktur eines Induktionsbeweises einzuhalten:
(1) | Induktionsvariable angeben: Manche Aussagen haben mehrere Variable (wie zum Beispiel das Kommutativgesetz). Es muss klar werden, wonach die Induktion geführt wird. |
(2) | Induktionsanfang angeben: Oft beginnen wir bei 0, manchmal aber auch bei 1 oder allgemein bei n0, wenn wir zeigen wollen, dass eine Aussage für alle n ≥ n0 gilt. |
(3) | Induktionsschritt angeben: Der Standardschritt führt von n nach n + 1. Aber auch ein Schritt von n − 1 nach n ist möglich und manchmal vorteilhaft. |
(4) | Induktionsvoraussetzung angeben: Die Induktionsvoraussetzung sollte explizit notiert werden. Es ist guter Stil, ihre Verwendung im Folgenden kenntlich zu machen, etwa durch „nach I.V. gilt“. |
Wir führen den Induktionsschritt zur Illustration noch einmal von n − 1 nach n durch:
Beweis der Gauß-Summenformel, Variante
… (wie oben)
Induktionsschritt von n − 1 nach n:
Es gelte ∑k ≤ n − 1 k = (n − 1)n/2 (I.V.). Wir zeigen:
∑k ≤ n k = n(n + 1)2.
Es gilt
| ∑k ≤ n k | = n + ∑k ≤ n − 1 k =I.V. n + (n − 1) n2 = n (1 + n − 12) |
| = n (2 + n − 12) = n (n + 1)2. |
Für Formeln wie die Gauß-Summe besteht der Induktionsschritt im Wesentlich aus Termumformungen unter Verwendung der Induktionsvoraussetzung: Die linke Seite wird durch mehrere Rechenschritte in die rechte Seite umgeformt. Hierzu kann es hilfreich sein, das Ziel des Induktionsschritt konkret anzugeben (im Beweis in der Form „Wir zeigen, dass …“). Diese Angabe verdeutlicht die Form, die wir durch die Termumformung anstreben.
Zur Entdeckung der Summenformel
Wie kommt man auf die Summenformel von Gauß? Der Induktionsbeweis gibt keine Auskunft. Eine Möglichkeit ist, die ersten Summen auszurechnen:
0 = 0, 0 + 1 = 1, 0 + 1 + 2 = 3, 0 + 1 + 2 + 3 = 6, 0 + 1 + 2 + 3 + 4 = 10, …
Es ergibt sich die Folge
0, 1, 3, 6, 10, 15, 21, 28, …
Verdoppeln liefert 0, 2, 6, 12, 20, 30, 42, 56, … Nun lässt sich die Formel n(n + 1) raten und eine Halbierung liefert die Gauß-Summe. Eine Alternative, in einer Summe wie
0 + 1 + 2 + … + 98 + 99 + 100
zu beobachten, dass sich die Summanden paarweise zu 100 addieren, wenn wir sie von vorne und hinten zusammenfassen. Es gibt 50 + 1/2 derartige Paare (0 + 100, …, 49 + 51; die 50 in der Mitte bleibt alleine), sodass
∑k ≤ 100 k = 100 · 1012.
Eine Verallgemeinerung führt zur Summenformel n(n + 1)/2. Diese „Gauß-Methode“ liefert einen alternativen Beweis der Formel. Es muss also nicht immer Induktion sein − eine clevere Idee reicht auch.