1Sums

Let’s recall the Theorem “Kleiner Gauß”: Let $n\in \N$. Then the sum of all numbers between $1$ and $n$ is $n(n+1)/2$. There are (many) more theorems and other mathematical contexts that involve sums, and it would be cumbersome to always talk about the sum of all numbers of this and that form. Therefore, mathematicians have come up with a notation for sums. In this notation, Kleiner Gauß reads as follows: Let $n\in \N$. Then

Here, $\sum$ is the greek letter Sigma (for sum). When the sum appears in normal text, it is typeset as $\sum _{i=1}^n i$. In writing this, we are saying that we sum up all values $i$ for which $i$ is between $1$ (the lower summation bound) and $n$ (the upper summation bound). Hence, the summation variable $i$ “goes through” the values $1,2,...,n$, where the variable $n$ itself is a placeholder for an actual integer, for example $100$. If you have ever seen a loop variable in a programming language, this concept is familiar to you.

Gauß’ original insight that surprised his teacher can be obtained by setting $n$ to $100$:

For $n=0$ (the smallest natural number), the theorem would give us

This might look strange but is correct if we agree (as we previously did) that the sum is $0$ if the upper summation bound is smaller than the lower one.

With this notation, we can do more things. For example,

is the sum of the squares of the numbers between $1$ and $100$, so $1+4+9+16+\cdots +10000$. We don’t know what Gauß would have done if the task would have been to compute this sum, but we know that a significantly more complicated variant of Gauß’ trick still works and gives the answer for all upper summation bounds $n$: In particular,

Instead of squaring the summation variable $i$, we could apply any function $f$ that gives an answer $f(i)$ for every $i$ between the lower and the upper summation bound. At this point, the saving over the natural language becomes apparent. No one wants to write (or read) “the sum of all squares of the reciprocals of the numbers between $1$ and $n$”, when instead, we can write

Lower and upper summation bounds are integers, and they can also be negative. Summation variables are not always called $i$; in fact, $i,j,k$ are the most frequently used ones. So for example,

There are rare cases where the summation variable does not actually occur behind the $\Sigma$. For example, consider the sum

You may ask what this is good for, but apart from that, there is no reason to get confused. This sum is just $1+1+\cdots +1$, with one $1$ for every $k$ between $1$ and $10$. Hence, $\sum _{k=1}^{10} 1=10$.

2Summing over sets and conditions

Sometimes, it is unnatural or even impossible to write a sum in $\Sigma$‐notation in the way we did before. As an example, consider “the sum of all even numbers between $10$ and $100$” from Exercise 2. Here, the solution $\sum _{i=5}^{50} 2i$ seems to be a bit of a workaround. We would prefer to directly sum over the even numbers between $10$ and $100$. This can be done as follows. We let $S=\{ 10,12,...,100\}$ be the set of even numbers between $1$ and $100$ and then simply write

This notation means that the summation variable $i$ “goes through” all elements of the set $S$. In which order we go through $S$ doesn’t and shouldn’t matter, as the elements are in the bag $S$ in no particular order. Luckily, this works out, since summation is commutative, meaning that the result does not depend on the summation order. We have $1+2+3=6$ and also $3+1+2=6$.

In the previous example, we had to introduce an extra set constant $S$, or we could have written

Both variants have disadvantages. When reading $\sum _{i\in S} i$, the reader has to remember what $S$ was, and writing the set out explicitly, as in $\sum _{i\in \{ 10,12,...,100\} } i$, may look complicated, in particular if the set has no short notation.

Another alternative is the following:

Here, we have a condition below the $\Sigma$, and the meaning is that we sum over all $i$ satisfying the condition; in this case, being between $10$ and $100$ and even; so the semicolon in the condition stands for “and”.

There is no generally preferable notation here, it always depends on the sum in question. The goal should always be to write down the sum such that it is unambiguous and at the same time as readable as possible.

3Subscripts

Suppose we have a vector such as $(5,4,1,1,3,-6,8)$. Now we want to express “the sum of all elements of the vector” using $\Sigma$‐notation. How do we do this? The idea is simple:

Except that writing “$i$‐th element of $(5,4,1,1,3,-6,8)$” is cumbersome. You also realize that it doesn’t matter whether the vector is $(5,4,1,1,3,-6,8)$, and whether it has length $7$ to begin with. Using a variable for the vector, and one for its length, we can talk about the sum of all elements of an $n$‐vector $v$ as To simplify this further (and get rid of all remaining traces of prose), mathematicians prefer to write this as Here, the $i$ in $v_i$ is a subscript, and $v_i$ denotes the $i$‐th element of vector $v$. This also allows us to write the $n$‐vector $v$ as $v=(v_1,v_2,...,v_n)$. Let’s say we only want to sum up the elements of $v$ at odd positions, i.e. the first, the third, and so on. Then we can write where $S$ is the set of odd numbers between $1$ and $n$. Alternatively, we could write

There is another use of subscripts. We know how to talk about one function $f$, one set $S$, one natural number $n$, one real number $x$, and so on. But let’s say we want to talk about two or even more functions. We could call them $f,g,h,...$, but that way, we quickly run out of letters. It is more practical to talk about two functions called $f_1,f_2$, three sets called $S_1,S_2, S_3$, or four integers called $n_1,n_2,n_3,n_4$. When we have just two (maybe at most three) objects, for example integers, naming them $n,n',n''$ is also common.

4Matrices and two subscripts

A vector is tuple of numbers such as $v=(6,5,6,4,3)$. The first number is $v_1=6$, the second one is $v_2=5$, and so on. But sometimes, numbers are ordered in a two‐dimensional fashion. For example, if we specify a function with two arguments via a value table, the entries of the table form a two‐dimensional matrix. Recall the example from before, $f(x,y)=x^y$ with value table

The function values form a $5\times 5$‐matrix

a two‐dimensional collection of numbers. How would we sum up all elements of $M$ in $\Sigma$‐notation? We would write Here, $M_{i,j}$ has two subscripts, one for the row and one for the column. So $M_{i,j}$ is the element of $M$ in row $i$ and column $j$. For example, $M_{2,4}=3$ and $M_{4,1}=0$ in the example above. Sometimes, you also see $M_{ij}$ (subscripts not separated by a comma), and this works fine if the subscripts are variables. But if they are not, then there is a problem: writing $M_{24}$ instead of $M_{2,4}$ could create confusion; the reader might think that $M_{24}$ is the $24$‐th element of a vector called $M$.

In $\sum _{i=1}^5\sum _{j=1}^5 M_{i,j}$, we have a double sum. This is to be read as

i.e. in evaluating the double sum, we first compute the five inner sums $\sum _{j=1}^5 M_{i,j}$ for $i=1,2,3,4,5$; the outer sum then adds up these 5 inner sums. Using conditions, this can also be written as a single sum This means that $i$ and $j$ go through all possible combinations where both $i$ and $j$ are between $1$ and $5$.

We can also have three or more subscripts if numbers are ordered in a three‐ or even higher‐dimensional structure, but this is rarely needed, so we will not discuss it.

An obvious but useful feature of double sums is that the order of summation can be interchanged without changing the result. If $M$ is an $n\times m$ matrix ($n$ rows, $m$ columns), then

Indeed, the first double sum adds up the elements of $M$ row by row: each inner sum is the sum of all elements in one row. The second double sum adds up the elements column by column: each inner sum is the sum of all elements in one column. But as summation is commutative, it doesn’t matter whether we sum rowwise or columnwise, the result will always be the same.

5Back to sets

Subscripts and conditions—so far just defining ranges to sum over—can directly be used to define sets, not only in the context of sums. For example, the set of all natural numbers between 1 and 100 (that we have previously written as $\{ 1,2,...,100\}$ could also be defined as $\{ i\in \N : 1\leq i\leq 100\}$. This notation means that the set consists of all natural numbers $i$ that satisfy the condition after the colon. Unlike for example in the sum

we have to say that what kind of number the set contains, and by writing $i\in \N :...$, we indicate that these are natural numbers. In the sum, this extra piece of information is not needed, since summation variables are integers anyway.

This way of defining sets is really flexible and lets you express many things in a concise way. As an example, let’s imagine that you are repeatedly running some track, and each time you record your run time (in minutes rounded down, say). If you have run the track a total of $n$ times, the result is an $n$‐vector $v$ that may look like this: $(19, 18, 19, 20, 17, 17, 16, 17, 16, 15)$. Now you want to know in which runs you have beaten your previous record. In the example, these are the runs 2, 5, 7, 10.

But now, given any $n$‐vector $v$, how do you express the set of runs in which you have beaten your previous record? Here is a way to do it, using conditions, subscripts, and functions (we also always have those!):

Here, $\min$ is a (quite self‐explanatory) function that can take several arguments and does the natural thing: the function value is the minimum (the smallest) value among its arguments. Then the condition $v_i < \min (v_1,...,v_{i-1})$ says that the run time in the $i$‐th run is smaller than in all the runs before, so the $i$‐th run establishes a new record. Hence, in the set $S$, we collect all runs between $2$ and $n$ that establish a new record.