# Summen von natürlichen Zahlen

1. Die ersten hundert natürlichen Zahlen
2. Summen von Quadrat- und Kubikzahlen
3. Summen höherer Potenzen

Diese Präsentation führt Sie – ausgehend von einer berühmten Anekdote – in die Verwendung des Summenzeichens ein und zeigt exemplarisch, wie die spielerische Beschäftigung mit Spezialfällen zu allgemeinen Erkenntnissen führen kann.

## 1. Die ersten hundert natürlichen Zahlen

Eine berühmte Anekdote über Carl Friedrich Gauß, einen der größten Mathematiker aller Zeiten, beginnt in der Version aus Daniel Kehlmanns Roman „Die Vermessung der Welt“ so:

Der Lehrer in der Schule hieß Büttner und prügelte gern. [...]

Büttner hatte ihnen aufgetragen, alle Zahlen von eins bis hundert zusammenzuzählen. Das würde Stunden dauern, und es war beim besten Willen nicht zu schaffen, ohne irgendwann einen Additionsfehler zu machen, für den man bestraft werden konnte. Na los, hatte Büttner gerufen, keine Maulaffen feilhalten, anfangen, los! Später hätte Gauß nicht mehr sagen können, ob er an diesem Tag müder gewesen war als sonst oder einfach nur gedankenlos. Jedenfalls hatte er sich nicht unter Kontrolle gehabt und stand nach drei Minuten mit seiner Schiefertafel, auf die nur eine einzige Zeile geschrieben war, vor dem Lehrerpult.

Natürlich können wir den Computer solche Summen berechen lassen. Der schafft das durch stures Aufaddieren in praktisch nicht wahrnehmbarer Zeit. Dieser Komfort kann uns aber leider auch von der Entwicklung einer effizienten Lösung abhalten. Wenn wir dann nicht die Summe von 1 bis 100 sondern z.B. bis 10100 benötigen, scheitert auch der schnellste Computer. Nachdenken lohnt sich auch heute noch!

### Das Summenzeichen

Die gesuchte Summe ist

1+2+3+\ldots+100

Ist das nicht eine etwas schwammige Schreibweise?

Tatsächlich bleibt es dem Leser überlassen, die Bedeutung der drei Punkte zu erfassen. Ihnen ist wahrscheinlich sofort klar, was z.B. mit

1+2+4+8+16+\ldots+1024

gemeint ist. Trotzdem verwendet man die Pünktchen-Schreibweise in der Praxis nur mit gleichbleibenden Abständen.

Klarer und kürzer kann man Summen mit dem Summensymbol (großer griechischer Buchstabe Sigma) schreiben:

\sum_{i=1}^{100} i

Damit werden für i der Reihe nach alle Werte vom Anfangswert 1 bis zum Endwert 100 eingesetzt und aufsummiert.

Statt der Laufvariablen i kann rechts auch ein beliebiger Term stehen, der jeweils in Abhängigkeit von i berechnet wird:

\sum_{i=n_0}^{n_1} f(i)

Die Bedeutung einer solchen Summe könnte man in mathGUIde allgemein so definieren:

    def sigma(n0, n1, f):
        sum = 0         # anfangs leere Summe
        i = n0          # i auf Startwert setzen
        while i <= n1:  # solange i den Endwert nicht überschreitet...
            sum += f(i) # ...die Summe um f(i) erhöhen
            i += 1      # ...und i um eins erhöhen
        return sum

Wieso kommt in der Parameterliste der Funktion `sigma` die Variable i nicht vor? Das hat einen guten Grund: i dient ja nur als Hilfsvariable für das Durchzählen der in die Summe einzusetzenden Werte. Man könnte dafür auch eine beliebige andere Variable nehmen, ohne den Wert der Summe zu verändern. In der Implementierung haben wir dafür willkürlich die lokale Variable `i` verwendet.

Dass die Laufvariable nicht prinzipiell zur Summe gehört, sondern nur ein Hilfsmittel in der Implementierung ist, zeigt die folgende rekursive Implementierung, die ganz ohne lokale Variablen auskommt:

    def sigma(n0, n1, f):
        if n0 > n1:   # Startwert ist schon größer als Endwert!
            return 0
        else:         # Summe der Funktionswerte von Startwert und Rest
            return f(n0) + sigma(n0+1, n1, f)

In Python gibt es mit dieser Variante leider ein technisches Problem: Wegen der begrenzten Rekursionstiefe funktioniert sie nur bei nicht allzu großer Laufweite.
Manche Programmiersprachen erkennen hier, dass der rekursive Funktionsaufruf die letzte Aktion zur Berechnung des Funktionswerts ist, und optimieren ihn weg.

In unserem Beispiel ist f(i) = i, n0 = 1 und n1 = 100.
Damit können wir die gesuchte Summe so berechnen:

    def f(i):
        return i
    sigma(1, 100, f)

Das ist aber etwas umständlich, dass man erst eine Funktion definieren muss, die man nur einmal benötigt!

Ja, deshalb gibt es auch die Möglichkeit, eine anonyme Funktion zu verwenden:

    sigma(1, 100, lambda i:i)

Mit dem Schlüsselwort `lambda` beginnt man in Python die Definition einer anonymen Funktion. Danach folgen, durch Komma getrennt, die Parameter (hier nur einer) und dann nach einem Doppelpunkt der Funktionswert.

### Kleine Übungen zum Summenzeichen

Bitte prüfen Sie Ihr Verständnis des Summenzeichens an den folgenden Beispielen:

\sum_{i=2}^4 {i^2} \quad \quad \sum_{k=-1}^1 {k^4} \quad \quad \sum_{i=1}^{10} 3 \quad \quad \sum_{i=1}^{0} (i+5) \quad \quad

Bevor Sie mathGUIde die Lösungen anzeigen lassen, versuchen Sie es bitte erst selbst!
Als Gedächtnisstütze können Sie die Definition der Funktion `sigma` noch einmal ins Eingabefenster kopieren.

    sigma( 2,  4, lambda i: i^2)
    sigma(-1,  1, lambda k: k^4)
    sigma( 1, 10, lambda i: 3)
    sigma( 1,  0, lambda i: i+5)

Die dritte Summe sieht zwar etwas ungewöhnlich aus, ist aber durchaus korrekt: Im Term hinter dem Summenzeichen kommt die Laufvariable gar nicht vor. Hier wird also zehnmal der konstante Wert 3 aufsummiert.
Auch die vierte Summe ist ungewöhnlich: Der Endwert der Laufvariable ist kleiner als der Anfangswert. Was passiert hier mit der while-Schleife in der Definition von `sigma`?

### Die Gauß'sche Lösung des Problems

Hat Gauß denn wirklich alle 100 Zahlen einzeln addiert?

Bei Kehlmann geht die Anekdote so weiter:

So, sagte Büttner und griff nach dem Stock. Sein Blick fiel auf das Ergebnis, und seine Hand erstarrte. Er fragte, was das solle.

Fünftausendfünfzig.

Was?

Gauß versagte die Stimme, er räusperte sich, er schwitzte. Er wünschte nur, er wäre noch auf seinem Platz und rechnete wie die anderen, die mit gesenktem Kopf dasaßen und taten, als hörten sie nicht zu. Darum sei es doch gegangen, eine Addition aller Zahlen von eins bis hundert. Hundert und eins ergebe hunderteins. Neunundneunzig und zwei ergebe hunderteins. Achtundneunzig und drei ergebe hunderteins. Immer hunderteins. Das könne man fünfzigmal machen. Also fünfzig mal hunderteins. Büttner schwieg. Fünftausendfünfzig, wiederholte Gauß, in der Hoffnung, daß Büttner es ausnahmsweise verstehen würde.

Diese Paarbildung geht auf, weil Hundert eine gerade Zahl ist. Damit es auch für ungerade Zahlen funktioniert, schreiben wir die Summe zweimal auf, einmal vorwärts und einmal rückwärts:

\begin{eqnarray} & 1 & + & 2 & + & 3 & + & \ldots & + &98 & + & 99 & + & 100 \\ = & 100 & + & 99 & + & 98 & + & \ldots & + & 3 & + & 2 & + & 1 \end{eqnarray}
Die Summe von 1 bis 5 lässt sich zweimal in einem 5·6-Rechteck unterbringen.

so ergeben die übereinanderstehenden Zahlen jeweils 101.
Die doppelte Summe ist also 100·101 = 10100 und damit die einfache Summe 5050.

Für allgemeinere Summen von 1 bis n ergibt sich auf diese Weise:

2 \sum_{i=1}^n i = n(n+1)
und damit:
\sum_{i=1}^n i = \frac{n(n+1)}2

Zur Belohnung für unser Nachdenken rechnet mathGUIde uns jetzt mal eben die Summe der natürlichen Zahlen bis 10100 aus. Der Operator `//` steht für ganzzahlige Division:

    n = 10^100
    print(n*(n+1) // 2)

Fortsetzung: Summen von Quadratzahlen