Eine häufige Aufgabe ist die Aufsummierung von vielen Zahlenwerten, z.B. in der Form von Elementen einer Menge. In diesem Abschnitt werden wir eine kompakte Schreibweise hierfür einführen sowie einige Standardtechniken vorstellen, um Summen effizient zu berechnen.
Zur Darstellung von Summen verwenden wir das Summationszeichen \(\Sigma\). Es handelt sich hierbei um den griechischen Großbuchstaben Sigma. In Zusammenhang mit Summen spricht man dieses Symbol aus als "Summe".
Häufig will man Elemente mit bestimmten Eigenschaften, z.B. Elemente einer Menge oder Zahlenwerte aus einem bestimmten Zahlenbereich, aufsummieren. Je nachdem, was man mit der Summe ausdrücken möchte, gibt es hierfür unterschiedlichste Schreibweisen. Die gebräuchlichsten wollen wir im Folgenden kurz vorstellen.
Eine Möglichkeit, Elemente aufzusummieren, besteht darin, diese Elemente mit einem Index, dem sogenannten Laufindex, zu versehen, und dann die Summe über alle Elemente mit einem bestimmten Index zu bilden. In der Regel gibt man hierfür einen Start- und einen Endwert für den Laufindex an. Den Laufindex schreibt man als tiefer gestellten Index an die Elemente, während man Start- und Endwert unter- bzw. oberhalb des Summenzeichens notiert. Um beispielsweise die Zahlen \(z_1, z_2, \dots, z_n\) aufzusummieren, also den Wert \(z_1 + z_2 + \dots + z_n\) zu bilden, könnte man Folgendes schreiben: \[\sum\limits_{i = 1}^{n}{z_i}\] Man spricht dies aus als "Summe der \(z_i\) mit i von 1 bis n" oder als "Summe von i gleich 1 bis n der \(z_i\)."
Gelegentlich schreibt man aus Platzgründen Start- und Endwert auch rechts neben das Summensymbol statt darunter und darüber, also \(\sum_{i = 1}^{n}{z_i}\). Die Bedeutung ist die gleiche.
Alternativ kann man Start- und Endwert auch zu einer Bedingung für den Laufindex zusammenfassen und äquivalent zu obigem Ausdruck Folgendes schreiben: \[\sum\limits_{1 \leq i \leq n}{z_i}\] Wie man sieht haben Summen in diesen Schreibweisen eine gewisse Ähnlichkeit mit den aus der Informatik bekannten for-Schleifen.
Für Start- und Endwert können wir jeweils sowohl Variablen als auch konkrete Zahlenwerte verwenden. Die Buchstaben für die Indizes können wir, wie in der Mathematik üblich, beliebig wählen. Häufig verwendet man hierfür die Buchstaben i, j, k, l, m und n.
Alternativ können wir eine Summe auch ohne Angabe von Start- und Endwert schreiben, indem wir Elemente mit einer bestimmten Eigenschaft, z.B. Elemente einer bestimmten (Teil-)Menge, aufsummieren. Statt Start- und Endwert geben wir in diesem Fall eine Bedingung für die Elemente an. Um beispielsweise alle Elemente a einer endlichen Menge A aufzusummieren, könnten wir Folgendes schreiben: \[\sum\limits_{a \in A}{a}\]
Wir können die Angabe einer Bedingung auch mit einem Start- und Endwert kombinieren. Um z.B. alle geraden Zahlen zwischen 0 und 100 aufzusummieren, könnten wir \[\sum_{\substack{k = 0 \\ k\text{ ist gerade}}}^{100}{k}\] schreiben.
Weitere Beispiele
Um n-mal die Zahl 7 aufzuaddieren, könnten wir Folgendes schreiben: \[\sum\limits_{i = 1}^{n}{7} = 7 + 7 + \dots + 7 = n \cdot 7\]
Wir können für den Endwert auch eine konkrete Zahl angeben, z.B. um fünfmal die 7 aufzuaddieren: \[\sum\limits_{j = 1}^{5}{7} = 7 + 7 + 7 + 7 + 7 = 5 \cdot 7 = 35\]
Statt einer festen Zahl können wir auch den Laufindex selbst innerhalb der Summe verwenden. Um z.B. alle natürlichen Zahlen zwischen 1 und 10 aufzusummieren können wir Folgendes schreiben: \[\sum\limits_{n = 1}^{10}{n} = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55\]
Der Startwert der Summation muss nicht immer bei 1 beginnen. Wir können hierfür beliebige andere Zahlen oder Variablen angeben, solange der Startwert stets kleiner als der Endwert ist. Mit folgender Formel können wir beispielsweise die natürlichen Zahlen zwischen 5 und 8 aufsummieren: \[\sum\limits_{k = 5}^{8}{k} = 5 + 6 + 7 + 8 = 26\]
Mit folgender Formel könnten wir alle ungeraden natürlichen Zahlen zwischen 1 und 10 aufsummieren: \[\sum_{\substack{i = 1 \\ i\text{ ist ungerade}}}^{10}{i} = 1 + 3 + 5 + 7 + 9 = 25\]
Um alle Elemente \(a_1, \dots, a_n\) mit ihrem jeweiligen Index zu multiplizieren und aufzusummieren, könnten wir Folgendes schreiben: \[\sum\limits_{i = 1}^{n}{i \cdot a_i} = 1 \cdot a_1 + 2 \cdot a_2 + \dots + n \cdot a_n\]
Um die Elemente \(a_1, \dots, a_n\) mit ihrem jeweiligen Vorgänger zu multiplizieren und aufzusummieren, könnten wir Folgendes schreiben (es ist zu beachten, dass wir in diesem Fall mit \(i = 2\) starten müssen, um \(i - 1\) korrekt bilden zu können!): \[\sum\limits_{i = 2}^{n}{a_i \cdot a_{i-1}} = a_2 \cdot a_1 + a_3 \cdot a_2 + \dots + a_n \cdot a_{n-1}\]
Wir können auch Summen aufaddieren und erhalten hierdurch Doppelsummen, also Summen von Summen, mit zwei Laufindizes: \[\sum\limits_{i = 1}^{m}{\sum\limits_{j = 1}^{n}{a_{ij}}} = \sum\limits_{i = 1}^{m}{(a_{i1} + a_{i2} + \dots + a_{in})}\] \[= (a_{11} + a_{12} + \dots + a_{1n}) + (a_{21} + a_{22} + \dots + a_{2n}) + \dots + (a_{m1} + a_{m2} + \dots + a_{mn})\]
Statt \[\sum\limits_{i = 1}^{m}{\sum\limits_{j = 1}^{n}{a_{ij}}}\] schreibt man häufig abgekürzt auch \(\sum_{\substack{1 \leq i \leq m \\ 1 \leq j \leq n}}{a_{ij}}\)
Wenn für die Summanden das Assoziativ- und das Kommutativgesetz gelten, dann dürfen die Summensymbole der Doppelsummen vertauscht werden, d.h. es gilt: \[\sum_{\substack{1 \leq i \leq m \\ 1 \leq j \leq n}}{a_{ij}} = \sum\limits_{i = 1}^{m}{\sum\limits_{j = 1}^{n}{a_{ij}}} = \sum\limits_{j = 1}^{n}{\sum\limits_{i = 1}^{m}{a_{ij}}} = \sum_{\substack{1 \leq j \leq n \\ 1 \leq i \leq m}}{a_{ij}}\]
Beweis:
Die Behauptung lässt sich durch Auflösung der Summe und anschließendes Umstellen der Summanden nachrechnen. Weil
nach Voraussetzung das Assoziativgesetz gilt, dürfen wir im ersten Schritt die Klammern um die Summen weglassen. Da weiterhin das
Kommutativgesetz gilt, dürfen wir im zweiten Schritt die Summanden beliebig vertauschen. Im dritten Schritt dürfen wir aufgrund
des geltenden Assoziativgesetzes neue Klammern setzen. Somit ergibt sich mit
\[\sum\limits_{i = 1}^{m}{\sum\limits_{j = 1}^{n}{a_{ij}}} = \sum\limits_{i = 1}^{m}{(a_{i1} + a_{i2} + \dots + a_{in})}\]
\[= (a_{11} + a_{12} + \dots + a_{1n}) + (a_{21} + a_{22} + \dots + a_{2n}) + \dots + (a_{m1} + a_{m2} + \dots + a_{mn})\]
\[= a_{11} + a_{12} + \dots + a_{1n} + a_{21} + a_{22} + \dots + a_{2n} + \dots + a_{m1} + a_{m2} + \dots + a_{mn}\]
\[= a_{11} + a_{21} + \dots + a_{m1} + a_{12} + a_{22} + \dots + a_{m2} + \dots + a_{1n} + a_{2n} + \dots + a_{mn}\]
\[= (a_{11} + a_{21} + \dots + a_{m1}) + (a_{12} + a_{22} + \dots + a_{m2}) + \dots + (a_{1n} + a_{2n} + \dots + a_{mn})\]
\[= \sum\limits_{j = 1}^{n}{(a_{1j} + a_{2j} + \dots + a_{mj})} = \sum\limits_{j = 1}^{n}{\sum\limits_{i = 1}^{m}{a_{ij}}}\]
die Behauptung. \(\square\)
Der vorhergehende Satz gilt in gleicher Weise für Doppelsummen von Produkten, also für Summen der Form \[\sum_{\substack{1 \leq i \leq m \\ 1 \leq j \leq n}}{a_ib_j} = \sum\limits_{i = 1}^{m}{\sum\limits_{j = 1}^{n}{a_ib_j}}\]
Wenn für die Summanden das Assoziativ- und das Kommutativgesetz gelten, dann dürfen die Summensymbole der Doppelsummen vertauscht werden, d.h. es gilt \[\sum_{\substack{1 \leq i \leq m \\ 1 \leq j \leq n}}{a_ib_j} = \sum\limits_{i = 1}^{m}{\sum\limits_{j = 1}^{n}{a_ib_j}} = \sum\limits_{j = 1}^{n}{\sum\limits_{i = 1}^{m}{a_ib_j}} = \sum_{\substack{1 \leq j \leq n \\ 1 \leq i \leq m}}{a_ib_j}\]
Beweis:
Unter Berücksichtigung des vorhergehenden Satzes gilt mit \(c_{ij} := a_ib_j\):
\[\sum\limits_{i = 1}^{m}{\sum\limits_{j = 1}^{n}{a_ib_j}} = \sum\limits_{i = 1}^{m}{\sum\limits_{j = 1}^{n}{c_{ij}}}\]
\[= \sum\limits_{j = 1}^{n}{\sum\limits_{i = 1}^{m}{c_{ij}}} = \sum\limits_{j = 1}^{n}{\sum\limits_{i = 1}^{m}{a_ib_j}}\]