Skip to main content

Section 4.2 Sums, Summation Notation

Subsection 4.2.1 Sigma Notation

Sigma notation uses the uppercase Greek letter sigma (\(\Sigma\)) as a convenient way to represent the sum of a sequence of terms. This is particularly helpful for sums with a large numbers of terms, including infinite sequences.

Definition 4.2.1.

Let \(\set{a_1, a_2, \dots, a_n}\) be a finite sequence of numbers. Then, the sum of the terms of the sequence is represented by,

\begin{equation*} \sum_{i=1}^n a_i = a_1 + a_2 + \dots + a_n \end{equation*}

The symbol \(\sum\) can be read as “the sum of”. The expression “\(\sum_{i=1}^n a_i\)” is read as the sum of \(a_i\) from \(i = 1\) to \(i = n\).

The terms \(a_i\) are an expression in \(i\text{.}\)

More generally, a summation can start at an integer other than 1.

Definition 4.2.2.

Let \(\set{a_m, a_{m+1}, \dots, a_n}\) be a finite sequence. Then, the sum of,

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

  • The \(i\) in the symbol is called the index of summation. Common letters include \(i, j, k\text{,}\) and sometimes \(l\text{.}\)

  • \(m\) and \(n\) are the limits of summation, called the lower limit and the upper limit, respectively.

The explicit evaluation of a sum (i.e. the right hand side of the equation) is called its expansion. To evaluate \(\sum_{i=m}^n a_i\text{,}\) evaluate \(f\) at each integer \(m, m + 1, \dots, n\) successively, and sum the results.

Note that the value of the summation is a number, and does not depend on the letter used for the index (it is a dummy variable). That is,

\begin{equation*} \sum_{i=1}^n a_i = \sum_{j=1}^n a_j \end{equation*}

Subsection 4.2.2 Evaluating Sums in Summation Notation

Subsection 4.2.3 Evaluating Sums in Summation Notation Using Python

Summations can be computed using Python. Recall that we defined a sequence using,

            seq = [a(i) for i in range(1,n+1)]

Then, we can use this to define a function which acts like sigma notation,

            def sigma(a,m,n):
                seq = [a(i) for i in range(m,n+1)]
                return(sum(seq))

This function creates the sequence seq, and return the sum of the terms in this sequence. This is basically the same as,

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

where \(a_i = a(i)\) are the terms of the sequence. Notice that in the function sigma, the index variable i is a dummy variable, just as it is in the summation.

Subsection 4.2.4 Linearity of Summation

Summation, or the sigma symbol, is linear, in that for functions \(f, g\text{,}\) and \(a, b \in \mathbb{R}\text{,}\)

\begin{equation*} \sum_{i=m}^n (af(i) + bg(i)) = a \sum_{i=m}^n f(i) + b \sum_{i=m}^n g(i) \end{equation*}

Intuitively, when summing finitely many numbers, the order in which they are added doesn't affect the value of the sum. Also, if all the numbers have a common factor, then it can be factored out and multiplied after the summation.

\begin{equation*} \sum_{i=1}^n (a_n + b_n) = (a_1 + b_1) + (a_2 + b_2) + \dots + (a_n + b_n) \end{equation*}

By the commutativity and associativity of addition, this sum can be rearranged with all the “\(a\)” terms first, and all the “\(b\)” terms after,

\begin{align*} \amp = (a_1 + a_2 + \dots + a_n) + (b_1 + b_2 + \dots + b_n)\\ \amp = \sum_{i=1}^n a_n + \sum_{i=1}^n b_n \end{align*}

Similarly,

\begin{align*} \sum_{i=1}^n ca_i \amp = ca_1 + ca_2 + \dots + ca_n\\ \amp = c\brac{a_1 + a_2 + \dots + a_n}\\ \amp = c \sum_{i=1}^n a_i \end{align*}

Subsection 4.2.5 Change of Index

Sums can start from any integer value. However, sums are often more convenient to manipulate and evaluate when the lower limit of summation is 1 (or 0 in some cases). Using a change of variable, we can change the starting index of a sum, and in particular convert a sum into an equivalent sum that starts at 1.

Consider the sum,

\begin{equation*} \sum_{i=3}^5 i^2 = 3^2 + 4^2 + 5^2 \end{equation*}

To convert the sum so it starts at 1, define a new variable \(j\text{,}\) given by \(j = i - 2\text{.}\) Then, when \(i\) starts at \(i = 3\text{,}\) the new variable will start at \(j = 1\text{,}\) as desired. Also, when \(i\) ends at \(i = 5\text{,}\) we have \(j = 3\text{,}\) so this is the upper limit of the summation. This means the sum is now of the form,

\begin{equation*} \sum_{j=1}^3 \end{equation*}

Finally, the expression for the general term \(i^2\) must be written in terms of the new variable \(j\text{.}\) To do this, substitute \(i = j + 2\) in the summation. This gives,

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

Notice that evaluating this sum gives the same numbers, in particular,

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

Also, since \(j\) is a dummy variable, it can be replaced by any other letter, including the original letter \(i\text{.}\) Then, the sum is also,

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

Thus,

\begin{equation*} \sum_{i=3}^5 i^2 = \sum_{i=1}^3 (i + 2)^2 \end{equation*}

Note that all of the sums,

\begin{equation*} \sum_{i=m}^{m+n} f(i) \qquad \sum_{i=0}^n f(i+m) \qquad \sum_{i=1}^{n+1} f(i+m-1) \end{equation*}

represent the same expansion, in particular,

\begin{equation*} f(m) + f(m+1) + f(m+2) + \dots + f(n) \end{equation*}

Subsection 4.2.6 Evaluating Sums

Some sums can be written as a closed form expression, which in this case basically means an expression, or formula, that doesn't include the \(\sum\) notation, and without “\(\dots\)”.

Subsection 4.2.7 Recursive Definition

Summation has a recursive definition. This follow from the identity,

\begin{equation*} \sum_{i=m}^m a_i = a_m \qquad \text{and} \qquad \sum_{i=m}^n a_i = \sum_{i=m}^{n-1} a_i + a_n \quad \text{for integers $n > m$} \end{equation*}

This can be written in Python as,

            def sigma(a,m,n):
                if n == m:
                    return(a(m))
                else:
                    return(sigma(a,m,n-1) + a(n))

Subsection 4.2.8 Sum of the First \(n\) Natural Numbers (Gauss's Problem)

One of the most famous stories in mathematics is the story of the mathematician Gauss. However, it is not known whether or not this actually took place. It goes as follows: In elementary school, the teacher asked Gauss's class to add up the first 100 positive integers (i.e. \(1 + 2 + 3 + \dots + 99 + 100\)). The idea was that it would be a time-killer, however Gauss (being gifted in math) recognized a pattern and figured out a method to calculate the sum quickly.

He noticed that if you split the “bent” the sum in half and “wrapped” it around the bottom, the numbers could be arranged as,

\begin{align*} \amp 1 \quad + 2 \:\: + \: 3 + \cdots + 48 + 49 + 50\\ \amp 100 + 99 + 98 + \cdots + 53 + 52 + 51 \end{align*}

Each vertical pair (\(1 + 100, 2 + 99, 3 + 98\text{,}\) and \(48 + 53\text{,}\) etc.) each add up to 101. Also, there are 50 of these pairs, so the total sum is \(50(101) = 5050\text{.}\) However, you'll notice that this specific method only works for an even count of numbers, since they will have to be paired up.

More generally, a similar method can be applied to find a formula for the sum of the first \(n\) natural numbers.

Let \(S\) be the desired sum, so that,

\begin{equation*} S = 1 + 2 + 3 + \dots + (n - 1) + n \end{equation*}

Then, copy the sum and arrange the terms in opposite order, as,

\begin{align*} S \amp = 1 + \quad \ 2 \quad \ + \quad \ 3 \quad \ + \dots + (n - 2) + (n - 1) + n\\ S \amp = n + (n - 1) + (n - 2) + \dots + \quad \ 3 \quad \ + \quad \ 2 \quad \ + 1 \end{align*}

Each vertical pair (\(1 + n\text{,}\) \(2 + (n - 1)\text{,}\) \(3 + (n - 2)\text{,}\) etc.) adds up to \(n + 1\text{,}\) and there are \(n\) terms. Thus, adding the two rows,

\begin{equation*} 2S = n(n + 1) \end{equation*}

Finally, solving for \(S\text{,}\) by dividing both sides by 2,

\begin{equation*} S = \frac{n(n + 1)}{2} \end{equation*}

Consider a staircase arrangement, which represents \(1 + 2 + \dots + n\text{.}\) This forms a staircase with length \(n\) along the bottom, and \(n\) along the left. Doubling this arrangement gives a rectangular array of length \(n\) and \(n + 1\text{,}\) which makes it clear that twice the sum \(1 + 2 + \dots + n\) is equal to the area of the rectangle \(n(n + 1)\text{.}\) Thus, the sum itself is half this amount, or \(1 + 2 + \dots + n = \frac{n(n + 1)}{2}\text{.}\) Note that this is equivalent to the fact that the \(n\)th triangular number is given by \(T_n = \frac{n(n + 1)}{2}\text{.}\)

Subsection 4.2.9 Sum of the First n Odd Natural Numbers

Consider adding consecutive odd numbers,

\begin{align*} 1 \amp + 3 = 4\\ 1 \amp + 3 + 5 = 9\\ 1 \amp + 3 + 5 + 7 = 16\\ 1 \amp + 3 + 5 + 7 + 9 = 25\\ \amp \vdots \end{align*}

There is a pattern that every sum is a perfect square, \(4 = 2^2, 9 = 3^2, 16 = 4^2, 25 = 5^2\text{,}\) etc.

The key insight is that odd numbers create “L” shapes. Arranging these pieces of area \(1, 3, 5, 7, \dots,\) up to \(2n-1\text{,}\) next to each other, forms a square, of side length \(n\text{,}\) which has area \(n^2\text{.}\)

By linearity of summation,

\begin{equation*} \sum_{k=1}^n (2k - 1) = 2 \sum_{k=1}^n k - \sum_{k=1}^n 1 \end{equation*}

Then, applying the sum of the first \(n\) natural numbers, and that \(\sum_{k=1}^n 1 = n\text{,}\)

\begin{align*} \amp = 2 \cdot \frac{n(n + 1)}{2} - n\\ \amp = n(n + 1) - n\\ \amp = n^2 \end{align*}

Subsection 4.2.10 Telescoping Sums

Consider the sum,

\begin{equation*} \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \dots + \frac{1}{n(n + 1)} = \sum_{k=1}^n \frac{1}{k(k + 1)} \end{equation*}

Evaluating this sum requires using the “trick” of the algebraic identity,

\begin{equation*} \frac{1}{k(k + 1)} = \frac{1}{k} - \frac{1}{k + 1} \end{equation*}

Thus, the sum can be written as,

\begin{align*} \sum_{k=1}^n \frac{1}{k(k + 1)} \amp = \sum_{k=1}^n \brac{\frac{1}{k} - \frac{1}{k + 1}}\\ \amp = \brac{1 - \frac{1}{2}} + \brac{\frac{1}{2} - \frac{1}{3}} + \dots + \brac{\frac{1}{n - 1} - \frac{1}{n}} + \brac{\frac{1}{n} - \frac{1}{n + 1}} \end{align*}

All of the terms cancel out, except for the leading 1 and the ending \(-\frac{1}{n+1}\text{.}\)

\begin{align*} \amp = 1 - \frac{1}{n + 1}\\ \amp = \frac{n}{n + 1} \end{align*}

Thus,

\begin{equation*} \boxed{\sum_{k=1}^n \frac{1}{k(k + 1)} = \frac{n}{n + 1}} \end{equation*}

More generally, a telescoping sum is of the form,

\begin{equation*} \sum_{i=m}^n \brac{f(i + 1) - f(i)} \end{equation*}

Expanding this sum,

\begin{align*} \amp \sum_{i=m}^n \brac{f(i + 1) - f(i)}\\ \amp = \brac{f(m + 1) - f(m)} + \brac{f(m + 2) - f(m + 1)} + \brac{f(m + 3) - f(m + 2)} + \dots\\ \amp \qquad \dots + \brac{f(n - 1) - f(n - 2)} + \brac{f(n) - f(n-1)} + \brac{f(n + 1) - f(n)} \end{align*}

All of the terms cancel out except for the first and last terms, and the result is,

\begin{equation*} \sum_{i=m}^n \brac{f(i + 1) - f(i)} = \underbrace{f(n + 1)}_{\text{last term}} - \underbrace{f(m)}_{\text{first term}} \end{equation*}

Intuitively, it is called a telescoping sum because the sum expands like a telescope, and then collapses back into a short expression.

Subsection 4.2.11 Algebraic Proofs of Sum of Natural Numbers and Squares

First, consider the algebraic identity,

\begin{equation*} (k + 1)^2 - k^2 = 2k + 1 \end{equation*}

which is a rearrangement of the familiar expansion \((k + 1)^2 = k^2 + 2k + 1\text{,}\) and is true for all integers \(k\text{.}\) Then, consider the summation,

\begin{equation*} \sum_{k=1}^n \brac{(k + 1)^2 - k^2} = \sum_{k=1}^n (2k + 1) \end{equation*}

The right-hand side, by linearity of summation, is equal to,

\begin{equation*} \sum_{k=1}^n (2k + 1) = 2\sum_{k=1}^n k + \underbrace{\sum_{k=1}^n 1}_{n} = 2 \sum_{k=1}^n k + n \end{equation*}

The left hand side is a telescoping sum,

\begin{align*} \sum_{k=1}^n \brac{(k + 1)^2 - k^2} \amp = \brac{2^2 - 1^2} + \brac{3^2 - 2^2} + \dots + \brac{n^2 - (n-1)^2} + \brac{(n+1)^2 - n^2}\\ \amp = (n + 1)^2 - 1 \end{align*}

Thus, after simplification, the identity becomes,

\begin{equation*} (n + 1)^2 - 1 = 2 \sum_{k=1}^n k + n \end{equation*}

Then, the summation \(\sum_{k=1}^n k\) can be solved for algebraically in terms of \(n\text{,}\)

\begin{align*} \sum_{k=1}^n k \amp = \frac{(n + 1)^2 - 1 - n}{2}\\ \amp = \frac{\brac{n^2 + 2n + 1} - 1 - n}{2}\\ \amp = \frac{n^2 + n}{2}\\ \amp = \frac{n(n + 1)}{2} \end{align*}

A similar method can be used to prove the sum of the first \(n\) squares. This uses a binomial expansion, a telescoping sum, and the previous sums \(\sum_{k=1}^n k\) and \(\sum_{k=1}^n 1\text{.}\)

First, consider the algebraic identity,

\begin{equation*} (k + 1)^3 - k^3 = 3k^2 + 3k + 1 \end{equation*}

which, again, is a rearrangement of the binomial expansion,

\begin{equation*} (k + 1)^3 = k^3 + 3k^2 + 3k + 1 \end{equation*}

Then, summing both sides the of equation,

\begin{align*} \sum_{k=1}^n \brac{(k + 1)^3 - k^3} \amp = \brac{2^3 - 1^3} + \brac{3^2 - 2^2} + \dots + \brac{n^3 - (n-1)^3} + \brac{(n+1)^3 - n^3}\\ \amp = (n+1)^3 - 1 \end{align*}

Then,

\begin{align*} (n+1)^3 - 1 \amp = \sum_{k=1}^n \brac{3k^2 + 3k + 1}\\ \amp = 3 \sum_{k=1}^n k^2 + 3 \sum_{k=1}^n k + \sum_{k=1}^n 1\\ (n+1)^3 - 1 \amp = 3 \sum_{k=1}^n k^2 + 3 \cdot \frac{n(n + 1)}{2} + n \end{align*}

Then, solving for the sum \(\sum_{k=1}^n k^2\) gives the formula,

\begin{align*} \brac{n^3 + 3n^2 + 3n + 1} - 1 \amp = 3 \sum_{k=1}^n k^2 + \frac{3n(n + 1) + 2n}{2}\\ n^3 + 3n^2 + 3n \amp = 3 \sum_{k=1}^n k^2 + \frac{3n^2 + 5n}{2} \end{align*}

Then,

\begin{align*} 3 \sum_{k=1}^n k^2 \amp = \frac{2(n^3 + 3n^2 + 3n) - (3n^2 + 5n)}{2}\\ \amp = \frac{2n^3 + 3n^2 + n}{2}\\ \amp = \frac{n(2n^2 + 3n + 1)}{2}\\ \amp = \frac{n(n + 1)(2n + 1)}{2} \end{align*}

Thus,

\begin{equation*} \sum_{k=1}^n k^2 = \frac{n(n + 1)(2n + 1)}{6} \end{equation*}

Subsection 4.2.12 Sum of First n Cubes

Consider the picture

On the one hand, the area of this square, which has side length \(1 + 2 + \dots + n = \frac{n(n + 1)}{2}\text{,}\) is \(\brac{\frac{n(n + 1)}{2}}^2\text{.}\) On the other hand, we can determine it's area by adding up the individual L-shaped pieces. The area of the small square is \(1^2 = 1\text{.}\) The area of the second region is \((1 + 2) \cdot (1 + 2) = 3^2\text{,}\) minus the area of the first region, or,

\begin{equation*} 3^2 - 1^2 = 8 = 2^3 \end{equation*}

Similarly, the area of the third region is \((1 + 2 + 3)^2 = 6^2\text{,}\) minus the area of the second region,

\begin{equation*} 6^2 - 3^2 = 27 = 3^3 \end{equation*}

In general, the area of the \(k\)th region is the area of the square of side \(1 + 2 + \dots + k = \frac{k(k + 1)}{2}\text{,}\) minus the area of the \((k-1)\)-th region which is a square with side length \(1 + 2 + \dots + (k-1) = \frac{k(k - 1)}{2}\text{.}\) Thus, the area of the \(k\)th region is,

\begin{align*} \brac{\frac{k(k + 1)}{2}}^2 - \brac{\frac{k(k - 1)}{2}}^2 \amp = \frac{k^2(k+1)^2 - k^2(k-1)^2}{4}\\ \amp = \frac{k^2 (k^2 + 2k + 1 - (k^2 - 2k + 1))}{4}\\ \amp = \frac{k^2(4k)}{4}\\ \amp = k^3 \end{align*}

Thus, the sum of the area of the \(n\) L-shaped regions is precisely \(\sum_{k=1}^n k^3\text{,}\) and so,

\begin{equation*} \sum_{k=1}^n k^3 = \brac{\frac{n(n + 1)}{2}}^2 \end{equation*}

First,

\begin{equation*} (k + 1)^4 - k^4 = 4k^3 + 6k^2 + 4k + 1 \end{equation*}

Then,

\begin{align*} \sum_{k=1}^n \brac{(k + 1)^4 - k^4} \amp = \sum_{k=1}^n \brac{4k^3 + 6k^2 + 4k + 1}\\ (n + 1)^4 - 1 \amp = 4 \sum_{k=1}^n k^3 + 6 \sum_{k=1}^n k^2 + 4 \sum_{k=1}^n k + \sum_{k=1}^n 1\\ \amp = 4 \sum_{k=1}^n k^3 + 6 \cdot \frac{n(n + 1)(2n + 1)}{6} + 4 \cdot \frac{n(n + 1)}{2} + n \end{align*}

Then, solving for \(\sum_{k=1}^n k^3\) gives the formula,

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

Subsection 4.2.13 Sums of Higher Powers

The technique of deriving the formula for the sum of powers of \(k\text{,}\) \(k^p\) where \(p = 1, 2, 3\) can be used for higher (integer) powers of \(p\text{.}\) In general, this technique involves using the binomial expansion of \((k + 1)^{p+1}\text{.}\) Then, applying summation and recognize a telescoping sum. Then, use the closed-form formulas for all of the lower powers of \(p\text{.}\) Finally, solve algebraically for the sum \(\sum_{k=1}^n k^p\text{.}\) The method is the same, however, the algebra becomes more and more complicated. It is easier to use a computer algebra system to solve for the summation.

\begin{align*} (k + 1)^5 - k^5 \amp = 5k^4 + 10k^3 + 10k^2 + 5k + 1\\ \sum_{k=1}^n \brac{(k+1)^5 - k^5} \amp = \sum_{k=1}^n \brac{5k^4 + 10k^3 + 10k^2 + 5k + 1}\\ (n + 1)^5 - 1 \amp = 5 \sum_{k=1}^n k^4 + 10 \sum_{k=1}^n k^3 + 10 \sum_{k=1}^n k^2 + 5 \sum_{k=1}^n k + \sum_{k=1}^n 1\\ \amp = 5 \sum_{k=1}^n k^4 + 10 \cdot \frac{n^2(n+1)^2}{4} + 10 \cdot \frac{n(n+1)(2n+1)}{6} + 5 \cdot \frac{n(n + 1)}{2} + n \end{align*}

Then, solving for \(\sum_{k=1}^n k^4\) gives,

\begin{equation*} \boxed{\sum_{k=1}^n k^4 = \frac{n(n + 1)(2n + 1)(3n^2 + 3n - 1)}{30}} \end{equation*}

An observation is that in general, the summation of \(n\) terms of \(k^p\) is roughly proportional to \(n^{p+1}\text{.}\)

Subsection 4.2.14 Advanced Summation