Summation

Many algorithms involve loops. In order to work out the time functions for these algorithms, we need to use summations. We will learn how summations work and how to work with them.

Watch the video and then answer the questions below.

Key Points

• A summation is an adding up of lots of things.
• We write summations using sigma notation
• Converting from sigma notation to a polynomial expression requires some thought, and sometimes the use of some formulae.

Reading Sigma Notation

Sigma notation uses the Greek capital letter sigma to express a summation, like this;

\[ \sum_{i=1}^{4} i = 1 + 2 + 3 + 4 = 10 \]

Below the sigma, you have a variable and a lower bound, here i=1. At the top you have an upper bound, here n. You can read this as the sum of i with values of i between 1 and n (inclusive).

Sum of an Arithmetic Series

An arithmetic sequence is a list of numbers with a constant difference between them, e.g. 1, 2, 3, 4, 5, ... In this sequence, the number increases by 1 each time. If we add them up, we get an arithmetic series, e.g. 1 + 2 + 3 + 4 + 5 + .... To sum an arithmetic series you can use the formula:

\[ \sum_{i=1}^{n} a = n (\frac{a_1 + a_n}{2}) \]

Where \(n\) is the length of the sequence, and \(a_1\) is the first element and \(a_n\) is the last element.

Basically, you find the average size of an element, and multiply it my the number of elements there are.

Sum of the First n Natural Numbers

To find the sum of the first `n` natural numbers is related to this. Because we start on \(1\), and end on \(n\) the average value of a number is going to be \( \frac{n+1}{2} \)

\[ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \]

Sum of a Geometric Series

A geometric sequence is a list of numbers where each number is found my multiplying the previous number by a constant e.g. 1, 2, 4, 8, 16, .... In this sequence, the number doubles every time. If we add them up, we get a geometric series, e.g. 1 + 2 + 4 + 8 + 16 + ....

To sum a geometric series you can use the formula:

\[ \sum_{i=0}^{n-1} (ar^k) = a(\frac{1-r^n}{1-r}) \]

Sum of Squares of the first n natural numnbers

We will often find that we need to sum the squares of the first n natural numbers. For this we can use this formula:

\[ \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} \]

Questions

1. Check your understanding

1. Arithmetic and Geometric Sequences

Check Answers

2. Summations

Solve the folowing:

1. \( \sum_{i=1}^{10} 1 = \)
2. \( \sum_{i=1}^{10} a = \)
3. \( \sum_{i=1}^{10} i = \)
4. \( \sum_{i=1}^{10} i^2 = \)

Check Answers

3. Multiple Summations

Work from right to left, expanding the inner-most summation first.

1. \( \sum_{i=1}^{10} \sum_{j=1}^{10} 1 = \)
2. \( \sum_{i=1}^{10} \sum_{j=1}^{10} j = \)
3. \( \sum_{i=1}^{10} \sum_{j=1}^{10} i = \)

Check Answers

4. Tricky Summations

Solve the following:

1. \( \sum_{i=1}^{10} \sum_{j=1}^{10} 1 = \)
2. \( \sum_{i=1}^{10} \sum_{j=1}^{i} j = \)
3. \( \sum_{i=1}^{10} 2i^2 + 4i + 3 = \)

Check Answers

Summary

In this section we have learned about summation and how to work with sigma notation.

• You should be able to interpret sigma notation
• You should be able to solve equations that involve summations
• You should be able to apply the two summation formulas described above

Once you’ve answered the questions above you can move on to the challenges for this topic

Improve this page