Skip to main content

Section 5.3 Summation

In many contexts both practical and theoretical we would like to add together the terms of a sequence. This process occurs frequently enough to earn its own notation.

Definition 5.3.1.

The sum of the sequence \((a_i)_m^n\) is denoted

\begin{equation*} \sum_{i=m}^n a_i \end{equation*}

where the index \(i\) ranges from the lower bound of the sum, \(m\text{,}\) to the upper bound \(n\text{.}\) That is,

\begin{equation*} \sum_{i=m}^n a_i = a_m + a_{m+1} + a_{m+2} + \cdots + a_{n-1} + a_n \end{equation*}

The sum

\begin{equation*} \sum_{i=1}^4 i^2 \end{equation*}

is the sum of the sequence \((i^2)_1^4\text{,}\) where the lower bound is \(1\) and the upper bound is \(4\text{.}\) To calculate this sum, we calculate each term of the finite sequence \((i^2)_1^4\) and then add them all together.

\begin{align*} \sum_{i=1}^4 i^2 \amp = 1^2 + 2^2 + 3^2 + 4^2\\ \amp = 1 + 4 + 9 + 16\\ \amp = 30 \end{align*}

For the reader who has had some experience with programming, the expression

\begin{equation*} \sum_{i=m}^n a_i \end{equation*}

can be thought of as a for loop:

	sum = 0
	for i in range(m:n)
	    sum = sum + a(i)
	return sum

We can have sums of sums, and sums of sums of sums, etc. Double sums are common in computer science when evaluating the runtimes of doubly-nested for loops.

Consider the sum

\begin{equation*} \sum_{m=1}^3 \sum_{n=2}^4 (m+n) \end{equation*}

This sum is rectangular in the sense that the bounds of one sum are not determined by the other, and so we could do this sum in either order.

In one order, you may choose to sum over \(n\) first.

\begin{align*} \sum_{m=1}^3 \sum_{n=2}^4 (m+n) \amp = \sum_{m=1}^3 [(m+2) + (m+3) + (m+4)]\\ \amp = \begin{array}{r} 3 + 4 + 5 \\ + \; 4 + 5 + 6 \\ + \; 5 + 6 + 7 \end{array}\\ \amp = 12 + 15 + 18\\ \amp = 45 \end{align*}

Alternatively, you could iterate over \(m\) first.

\begin{align*} \sum_{m=1}^3 \sum_{n=2}^4 (m+n) \amp = \sum_{n=2}^4 (1+n) + \sum_{n=2}^4 (2+n) + \sum_{n=2}^4 (3+n)\\ \amp = \begin{array}{r} 3 + 4 + 5 \\ + \; 4 + 5 + 6 \\ + \; 5 + 6 + 7 \end{array}\\ \amp = 12 + 15 + 18\\ \amp = 45 \end{align*}

In the above calculation, each individual sum over \(n\) is calculated vertically. So the first column is the sum of \((1+n)\) from \(2\) to \(4\text{,}\) etc.

You can see that either way, the value of the sum is \(45\text{.}\)

Take the sum

\begin{equation*} \sum_{i=1}^4 \sum_{j=1}^i 2^{i+j} \end{equation*}

This time, the bounds of the \(j\)-sum are dependent on the value of \(i\text{.}\) When this happens, the best approach is to calculate the independent sum first. In this case, it means we'll start by iterating over \(i\text{.}\)

\begin{align*} \sum_{i=1}^4 \sum_{j=1}^i 2^{i+j} \amp = \sum_{j=1}^1 2^{j+1} + \sum_{j=1}^2 2^{j+2} + \sum_{j=1}^3 2^{j+3} + \sum_{j=1}^4 2^{j+4}\\ \amp = \begin{array}{r} 2^{1+1} + 2^{1+2} + 2^{1+3} + 2^{1+4} \\ + \; 2^{2+2} + 2^{2+3} + 2^{2+4} \\ + \; 2^{3+3} + 2^{3+4} \\ + \; 2^{4+4} \end{array}\\ \amp = \begin{array}{rrrr} 4 \amp + 8 \amp + 16 \amp + 32 \\ \amp + 16 \amp + 32 \amp + 64 \\ \amp \amp + 64 \amp + 128 \\ \amp \amp \amp + 256 \end{array}\\ \amp = 4 + 24 + 112 + 480\\ \amp = 620 \end{align*}

Notice that when one sum depends on the index of the other, the shape of the terms when written out is no longer “rectangular”, hence that language. This is because, for instance, the sum of \(2^{j+1}\) from \(j=1\) to \(1\) only has one term, whereas the sum of \(2^{j+4}\) from \(j=1\) to \(4\) has four terms.

Calculate the sum

\begin{equation*} \sum_{m=0}^2 \sum_{n=m}^{3m} m^2n \end{equation*}

Notice that this time, both the lower and upper bounds of the \(n\) sum depend on the value of \(m\text{.}\)

\begin{align*} \sum_{m=0}^2 \sum_{n=m}^{3m} m^2n \amp = \sum_{n=0}^{0} 0^2 \times n + \sum_{n=1}^{3} 1^2 n + \sum_{n=2}^6 2^2n\\ \amp = \begin{array}{rrrrrr} \amp 0 \amp + \amp 1 \amp + \amp 8 \\ \amp \amp + \amp 2 \amp + \amp 12 \\ \amp \amp + \amp 3 \amp + \amp 16 \\ \amp \amp \amp \amp + \amp 20 \\ \amp \amp \amp \amp + \amp 24 \\ \amp \amp \amp \amp + \amp 28 \end{array}\\ \amp = 114 \end{align*}