Summation Techniques

Loading [MathJax]/jax/output/HTML-CSS/jax.js

Summation Techniques

We have previously seen that sigma notation allows us to abbreviate a sum of many terms. Specifically, we know that $\sum_{i=0}^n a_i = a_0 + a_1 + a_2 + \cdots + a_n$

We have also seen several useful summation formulas we proved with the principle of mathematical induction, such as those shown in the table below:

$\displaystyle{\sum_{i=0}^n 1 = n+1}$	$\displaystyle{\sum_{i=0}^n i = \frac{n(n+1)}{2}}$
$\displaystyle{\sum_{i=0}^n i^2 = \frac{n(n+1)(2n+1)}{6}}$	$\displaystyle{\sum_{i=0}^n i^3 = \frac{n^2(n+1)^2}{4}}$
$\displaystyle{\sum_{i=0}^n i^4 = \frac{n^5}{5} + \frac{n^4}{2} + \frac{n^3}{3} - \frac{n}{30}}$

Suppose we wish to find a closed formula in terms of $n$ (i.e., a formula with no " $\cdots$ " in it) for the following sum where $p$ is some polynomial function.

$\sum_{i=0}^n p(i)$

Remembering both the formulas above (and related ones for higher powers, as needed) and the following two properties of summations, this is easy to do.

$\sum_{i=0}^n (a_i + b_i) = \sum_{i=0}^n a_i + \sum_{i=0}^n b_i \quad \quad \textrm{ and } \quad \quad \sum_{i=0}^n c \cdot a_i = c \sum_{i=0}^n a_i$

As an example, suppose we wanted to find a formula in terms of $n$ for $\displaystyle{\sum_{i=0}^n (4i^2-4i+1)}$ .

$\begin{array}{rcl} \displaystyle{\sum_{i=1}^{n} (4i^2 - 4i + 1)} &=& \displaystyle{\left[\sum_{i=1}^{n} 4i^2 \right] - \left[\sum_{i=1}^{n} 4i \right] + \left[\sum_{i=1}^{n} 1 \right] \quad \scriptsize{\textrm{ using the first property to split up the sum}}}\\\\ &=& \displaystyle{4 \left[\sum_{i=1}^{n} i^2 \right] - 4 \left[ \sum_{i=1}^{n} i \right] + n \quad \scriptsize{\textrm{ using the second property to pull out the coefficients}}}\\\\ &=& \displaystyle{4 \left[\frac{n(n+1)(2n+1)}{6} \right] - 4 \left[ \frac{n(n+1)}{2} \right] + (n+1) \quad \scriptsize{\textrm{using the formulas for } i^2, i, \textrm{ and } 1}}\\\\ &=& \displaystyle{\frac{2n(n+1)(2n+1)}{3} - \frac{6n(n+1)}{3} + \frac{3n+3}{3} }\\\\ &=& \displaystyle{\frac{4n^3+6n^2+2n-6n^2-6n+3n+3}{3}}\\\\ &=& \displaystyle{\frac{4n^3-n+3}{3}}\\\\ \end{array}$

However, not all summations involve polynomial functions. What if instead, we saw a summation whose terms could be written as a constant times the $i$ ^th power of some other constant.

As an example, suppose we wanted to find $\displaystyle{\sum_{i=0}^n \left(\frac{6 \cdot 3^i}{4^i}\right)}$ , which we see we could rewrite as $\displaystyle{\sum_{i=0}^n 6 \left(\frac{3}{4}\right)^i}$ .

Expanding the summation reveals its true nature:

$\displaystyle{\sum_{i=1}^n \left(\frac{6 \cdot 3^i}{4^i}\right) = 6 + 6 \left(\frac{4}{3}\right) + 6 \left(\frac{4}{3}\right)^2 + 6 \left(\frac{4}{3}\right)^3 + \cdots}$

Note how each term is $\frac{3}{4}$ times the one before it -- this is just a geometric series!

Recall the sum of a geometric series starting with $a$ and with common ratio $r$ is given by $\frac{a}{1-r}$ . This is a well-known result from precalculus -- but if you are curious where it comes from, consider the following argument:

Suppose $S = a + ar + ar^2 + ar^3 + \cdots$ . Then, $rS = ar + ar^2 + ar^3 + \cdots$ .

Subtracting the second from the first gives $S-rS = a$ .

Finally, factoring out the $S$ and dividing by the resulting $(1-r)$ then reveals $\displaystyle{S = \frac{a}{1-r}}$

which is what we hoped to show.

Returning to our example, we can then say that since the first term is $6$ and the common ratio is $\frac{3}{4}$ , the sum must be

$\frac{6}{1 - \frac{3}{4}} = 24$

Still, there are summations that we will want to find that involve neither polynomial functions or geometric sequences. We will not attempt to describe how to find every possible summation here -- that would be a near impossible task. However, there is one more very interesting type of summation that we should discuss ...a telescoping sum.

Consider the terms of the sum $\displaystyle{\sum_{i=1}^n \left(\frac{1}{i} - \frac{1}{i+2}\right)}$ .

Let's look at this sum in its expanded form:

$\left(\frac{1}{1} - \frac{1}{3}\right) + \left(\frac{1}{2} - \frac{1}{4}\right) + \left(\frac{1}{3} - \frac{1}{5}\right) + \left(\frac{1}{4} - \frac{1}{6}\right) + \left(\frac{1}{5} - \frac{1}{7}\right) + \left(\frac{1}{6} - \frac{1}{8}\right) + \cdots + \left(\frac{1}{n} - \frac{1}{n+2}\right)$

Notice how the terms of the middle can be grouped into pairs of terms that cancel each other.

$\left(\frac{1}{1} {\color{red}{- \frac{1}{3}}}\right) + \left(\frac{1}{2} {\color{blue}{- \frac{1}{4}}}\right) + \left({\color{red}{\frac{1}{3}}} {\color{green}{- \frac{1}{5}}}\right) + \left({\color{blue}{\frac{1}{4}}} {\color{magenta}{- \frac{1}{6}}}\right) + \left({\color{green}{\frac{1}{5}}} {\color{gray}{- \frac{1}{7}}}\right) + \left({\color{magenta}{\frac{1}{6}}} - {\color{gray}{\frac{1}{8}}}\right) + \cdots + \left({\color{gray}{\frac{1}{n}}} - \frac{1}{n+2}\right)$

Reordering the terms above so that these paired terms appear next to one another, we see how this sum can be made to "collapse" to only two terms from the beginning and two terms from the end of the original expansion.

$1 + \frac{1}{2} + \left({\color{red}{\frac{1}{3} - \frac{1}{3}}}\right) + \left({\color{blue}{\frac{1}{4} - \frac{1}{4}}}\right) + \left({\color{green}{\frac{1}{5} - \frac{1}{5}}}\right) + \left({\color{magenta}{\frac{1}{6} - \frac{1}{6}}}\right) + \cdots + \left({\color{brown}{\frac{1}{n} - \frac{1}{n}}}\right) - \frac{1}{n+1} - \frac{1}{n+2}$

After this collapse we find we have a nice and tiny formula for the sum in terms of $n$ ,

$\sum_{i=1}^n \left(\frac{1}{i} - \frac{1}{i+2}\right) = \frac{3}{2} - \frac{1}{n+1} - \frac{1}{n+2}$

In case you are still wondering why this is called telescoping sum, maybe the following clip from one of the Pirates of the Caribbean movies might help... 😊