Section3.4Summation Formulas

Subsection3.4.1Overview

In the previous section, we learned that accumulation sequences could be written using summation notation. Consequently, summations can always be interpreted in the context of a sequence. We have seen some examples where we could show that an accumulation sequence representing a summation was equivalent to a sequence defined explicitly. Unfortunately, that process is only useful if we can somehow discover the explicit formula to compare. We seek for computational methods that will allow us to find the explicit values for summations.

This section studies the properties of summation and their application. We will learn that any summation can be interpreted as a net change in an accumulation sequence. We will also learn about algebraic properties of summation, particularly a property known as linearity. Once we know summation formulas for elementary building blocks, these properties will allow us to combine them for more complicated formulas.

Subsection3.4.2Summation of as Net Accumulated Change

In the previous section, we learned that every accumulation sequence can be written using summation notation. The reverse is true. For every summation, we can define a corresponding accumulation sequence. Suppose we are interested in a summation

\begin{equation*} S = \sum_{k=m}^{n} x_k\text{,} \end{equation*}

where $m \gt 0$ and $n \ge m$ and $x=(x_k)$ is the sequence whose terms are being added. Let $u$ be any accumulation sequence with increments $x$ and initial value $u_0\text{.}$ Then we know we can write

\begin{equation*} u_k = u_0 + \sum_{i=1}^{k} x_i\text{.} \end{equation*}

We want to find the relation between the summation $S$ and the accumulation sequence.

First, we observe that the equation defining the accumulation sequence can be rewritten with the summation isolated:

\begin{equation*} \sum_{i=1}^{k} x_i = u_k - u_0\text{.} \end{equation*}

The summation is equal to the difference between the initial value and the final value of the accumulation sequence. This observation can be generalized to other index ranges, but to explain it we first need the splitting property of summation.

The property is simply a generalization of the associative properties of addition. The basic idea is to group terms,

\begin{align*} \sum_{i=m}^{n} x_i &= x_m + x_{m+1} + \cdots +x_{k} + x_{k+1} + \cdots + x_n\\ &= \big(x_m + x_{m+1} + \cdots +x_{k}\big) + \big(x_{k+1} + \cdots + x_n\big)\\ &= \sum_{i=m}^{k} x_i + \sum_{i=k+1}^{n} x_i \end{align*}

This splitting property allows us to rewrite a summation as a change in an associated accumulation sequence.

The accumulation sequence can be written

\begin{equation*} u_n = u_0 + \sum_{k=1}^{n} x_k. \end{equation*}

By the Summation Splitting Property, if we split the sum at index $k=m-1\text{,}$ we have

\begin{equation*} u_n = u_0 + \sum_{k=1}^{m-1} x_k+\sum_{k=m}^{n} x_k. \end{equation*}

However, once we recognize

\begin{equation*} u_{m-1} = u_0 + \sum_{k=1}^{m-1} x_k, \end{equation*}

we have

\begin{equation*} u_n = u_{m-1} + \sum_{k=m}^{n} x_k\text{.} \end{equation*}

Solving for the summation gives the stated conclusion,

\begin{equation*} \sum_{k=m}^{n} x_k = u_n - u_{m-1}. \end{equation*}

In this theorem, notice that which accumulation sequence is used does not matter. The initial value is irrelevant. In addition, notice that the accumulated change represented by the sum is equal to the change from one before the lower limit to the upper limit. This extra index step corresponds to increments matching backward differences. Finally, notice that the difference in accumulations can also be written

\begin{equation*} \sum_{k=m}^{n} x_k = \sum_{k=1}^{n} x_k - \sum_{k=1}^{m-1} x_k. \end{equation*}
Example3.4.3

In a previous example, we showed that the accumulation of odd integers was the sequence of squares. Use this to compute the sum of all odd three digit numbers.

Solution

The question is asking us to compute

\begin{equation*} 101+103+105+\cdots+997+999\text{.} \end{equation*}

In order to apply summation properties and accumulation sequences, we need the explicit formula for the sequence of terms as well as the lower limit and upper limit of the sum.

The sequence of odd integers $x=(1,3,5,\ldots)$ has an explicit formula $x_k=2k-1\text{,}$ $k=1,2,3,\ldots\text{.}$ It was for this sequence that we had 3.3.12

\begin{equation*} u_n = \sum_{k=1}^{n} 2k-1 = n^2. \end{equation*}

We want to write the sum of odd three digit numbers in terms of the sequence of increments. Then we will be able to use the explicit formula of the accumulation sequence to compute the sum.

To find the limits of summation, we need to find the value of the index $k$ such that $x_k=101$ (lower limit) and $x_k=999$ (upper limit). For the lower limit, we have

\begin{gather*} 2k-1 = 101\\ 2k=102\\ k=51, \end{gather*}

and for the upper limit we have

\begin{gather*} 2k-1 = 999\\ 2k=1000\\ k=500. \end{gather*}

Consequently, the sum of interest is

\begin{equation*} S= \sum_{k=51}^{500} 2k-1 = 101 + 103 + 105 + \cdots + 997 + 999. \end{equation*}

We are finally ready to apply the Summation as Net Accumulated Change. The summation is equal to the change in the accumulation sequence from 50 (index prior to first increment) to 500 (index of last increment),

\begin{align*} S = \sum_{k=51}^{500} 2k-1 &= u_{500} - u_{50}\\ &= 500^2 - 50^2\\ &= 250000 - 2500\\ &= 247500. \end{align*}

Subsection3.4.3Algebraic Properties of Summation

Now that we know that we can write a summation as the change of an accumulation sequence, we have a tool to compute summations once we are able to identify the accumulation. However, it can be tedious to find the accumulation sequence for every problem. We benefit from properties of summation that allow us to use elementary building blocks to compute the summation for a variety of different problems. These properties of summation correspond to the basic properties of addition.

Suppose we have a sequence $x$ and a constant $\alpha\text{.}$ We can create a new sequence $\alpha x\text{,}$ called a constant multiple, by multiplying every term of $x$ by the same constant $\alpha\text{.}$ Using the constant multiple as an increment sequence, every term will have a common factor of $\alpha\text{.}$ This leads to a property of summation called the constant multiple rule—constant multiples factor out of summation.

The next property considers a sequence that is itself formed by adding two sequences together. Suppose we have two sequences $u$ and $w$ and we form a new sequence $u+w$ with values that are the sum of the corresponding values, $(u+w)_n = u_n + w_n\text{.}$ Because addition is both commutative and associative, any sum of a finite number of terms can be regrouped in any convenient way. A summation of terms $u+w$ can therefore be grouped in a way that we add only the terms from $u$ and then add only the terms from $v$ and then add the results. This leads to a property of summation called the sum rule.

Using the rules together creates a new rule called linearity involving two sequences $x$ and $y\text{.}$ The idea for this rule is that an individual term in the increment sequence is the sum of a constant multiple of each, $\alpha x + \beta y\text{.}$ Such a sum is called a linear combination of $x$ and $y$ with coefficients $\alpha$ and $\beta\text{.}$ This name results from the general equation of a line being of the form $ax + by = c\text{.}$ Linearity applies the sum rule and the constant multiple as if in a single step.

Using $\alpha = 1$ and $\beta = -1\text{,}$ the linear combination becomes a difference, $\alpha x + \beta y = x - y\text{.}$ So the difference rule is a special case of linearity.

There are no corresponding rules for multiplication or division. This is really no different than emphasizing the importance of multiplying all terms using the distributive property, such as occurs with the FOIL method for multiplying binomials. For example, $\displaystyle \sum_{k=1}^{3} [k] = 1+2+3 = 6\text{.}$ The product of the sum gives one result:

\begin{equation*} \sum_{k=1}^{3}[k] \cdot \sum_{k=1}^{3}[k] = (1+2+3) \cdot (1+2+3) = 6 \cdot 6 = 36. \end{equation*}

But the sum of the products gives a different result:

\begin{equation*} \sum_{k=1}^{3}[k \cdot k] = (1^2+2^2+3^2) = 1+4+9 = 14. \end{equation*}

In general,

\begin{equation*} \sum_{k=m}^{n} [x_k \cdot y_k] \ne \sum_{k=m}^{n} x_k \cdot \sum_{k=m}^{n} y_k. \end{equation*}

Subsection3.4.4Elementary Summation Formulas

There are some elementary increment sequences for which we can find an explicit formula for the accumulation sequence. We will state the results and prove them using the uniqueness criteria for accumulation sequences 3.3.3. The simplest accumulation sequence, and that used in each of the elementary summation formulas, use an initial value $s_0 = 0\text{.}$ Thus, where we normally would have $s_n - s_0$ as the accumulated change, we only have $s_n\text{.}$

The accumulation sequence of interest is

\begin{equation*} \displaystyle u_n = \sum_{k=1}^{n} c\text{.} \end{equation*}

The increment sequence $x$ is a sequence of constants, $c_k=c\text{.}$ The proposed explicit sequence is

\begin{equation*} w_n = cn\text{.} \end{equation*}

The initial value of $u$ is $u_0 = 0$ which matches the initial value of the explicit sequence $w_0 = c(0) = 0\text{.}$ To show that $w=u\text{,}$ we need to show that $w$ has the same increments.

\begin{equation*} (\nabla w)_n = w_{n}-w_{n-1} = cn - c(n-1) = cn - cn + c = c \end{equation*}

Since $(\nabla w)_n = c$ is the same increment as $x_k\text{,}$ $u$ and $w$ are the same sequence.

The accumulation sequence of interest is

\begin{equation*} \displaystyle u_n = \sum_{k=1}^{n} k\text{.} \end{equation*}

The increment sequence $x$ is defined by $x_k=k\text{.}$ The proposed explicit sequence is

\begin{equation*} \displaystyle w_n = \frac{n(n+1)}{2}\text{.} \end{equation*}

The initial values agree:

\begin{align*} u_0 &= 0,\\ w_0 &= \frac{0(1)}{2} = 0. \end{align*}

The increment for $w$ is given by:

\begin{align*} (\nabla w)_n &= w_{n}-w_{n-1} = \frac{n(n+1)}{2} - \frac{(n-1)n}{2} \\ &= \frac{n}{2}\big( (n+1) - (n-1) \big) = \frac{n}{2} \cdot 2 = n \end{align*}

Since $(\nabla w)_n = n = x_n\text{,}$ $u$ and $w$ have the same increments and same initial value. By Theorem 3.3.3, $u$ and $w$ are equivalent.

The accumulation sequence of interest is

\begin{equation*} \displaystyle u_n = \sum_{k=1}^{n} k^2 \end{equation*}

so that increment sequence $x$ is defined by $x_k=k^2\text{.}$ The proposed explicit sequence is

\begin{equation*} \displaystyle w_n = \frac{n(n+1)(2n+1)}{6}\text{.} \end{equation*}

The initial values agree:

\begin{align*} u_0 &= 0,\\ w_0 &= \frac{0(1)(1)}{6} = 0. \end{align*}

The increment for $w$ is given by:

\begin{align*} (\nabla w)_n &= w_{n}-w_{n-1} \\ &= \frac{n(n+1)(2n+1)}{6} - \frac{(n-1)n\big(2(n-1)+1\big)}{6} \\ &= \frac{n}{6}\big( (n+1)(2n+1) - (n-1)(2n-1) \big) \\ &= \frac{n}{6} \big((2n^2+3n+1) - (2n^2-3n+1)\big) \\ &= \frac{n}{6}(6n) = n^2 \end{align*}

Since $(\nabla w)_n = n^2 = x_n\text{,}$ $u$ and $w$ have the same increments and same initial value. By Theorem 3.3.3, $u$ and $w$ are equivalent.

The accumulation sequence of interest is

\begin{equation*} \displaystyle u_n = \sum_{k=1}^{n} k^3 \end{equation*}

so that increment sequence $x$ is defined by $x_k=k^3\text{.}$ The proposed explicit sequence is

\begin{equation*} \displaystyle w_n = \frac{n^2(n+1)^2}{4}\text{.} \end{equation*}

The initial values agree:

\begin{gather*} u_0 = 0,\\ w_0 = \frac{0(1)(1)}{6} = 0. \end{gather*}

The increment for $w$ is given by:

\begin{align*} (\nabla w)_n &= w_{n}-w_{n-1} \\ &= \frac{n^2(n+1)^2}{4} - \frac{(n-1)^2n^2}{4} \\ &= \frac{n^2}{4}\big( (n+1)^2 - (n-1)^2 \big) \\ &= \frac{n^2}{4} \big((n^2+2n+1) - (n^2-2n+1)\big) \\ &= \frac{n^2}{4}(4n) = n^3 \end{align*}

Since $(\nabla w)_n = n^3 = x_n\text{,}$ $u$ and $w$ have the same increments and same initial value. By Theorem 3.3.3, $u$ and $w$ are equivalent.

The accumulation sequence of interest is

\begin{equation*} \displaystyle u_n = \sum_{k=0}^{n} b^k \end{equation*}

so that increment sequence $x$ is defined by $x_k=b^k\text{.}$ The proposed explicit sequence is

\begin{equation*} \displaystyle w_n = \frac{b^{n+1}-1}{b-1}\text{.} \end{equation*}

Because the summation lower index is 0, the sequence $u$ has a non-zero initial value $u_0 = b^0 = 1\text{.}$ The initial value of $w$ is given by

\begin{equation*} w_0 = \frac{b^{1}-1}{b-1} = 1, \end{equation*}

which matches the initial value of $u\text{.}$ The increment for $w$ is given by:

\begin{align*} (\nabla w)_n &= w_{n}-w_{n-1} = \frac{b^{n+1}-1}{b-1} - \frac{b^{n}-1}{b-1} \\ &= \frac{1}{b-1}\big( (b^{n+1}-1) - (b^n-1) \big) \\ &= \frac{b^{n+1}-b^n}{b-1} = \frac{b^n(b-1)}{b-1} = b^n \end{align*}

Since $(\nabla w)_n = b^n = x_n\text{,}$ $u$ and $w$ have the same increments and same initial value. By Theorem 3.3.3, $u$ and $w$ are equivalent.

Our first examples consider sums involving just the elementary terms.

Example3.4.13

Find the sum of the integers $1, 2, \ldots, 100\text{.}$

Solution

Start by recognizing this as the accumulation of the sequence $x=(k : k=1, 2, 3, \ldots)$ over a range $1 \le k \le 100\text{.}$ This allows us to rewrite our problem as a summation:

\begin{equation*} \sum_{k=1}^{100} k. \end{equation*}

Theorem Theorem 3.4.9 applies directly with $n=100\text{,}$ so we know

\begin{equation*} \sum_{k=1}^{100} k = \frac{100(101)}{2} = 5050. \end{equation*}
Example3.4.14

Find the sum of the integers $100, 101, \ldots, 200\text{.}$

Solution

This example uses the same basic sequence (the integers) but instead of starting at $k=1\text{,}$ we are summing the sequence $x = (k : k=1,2,3,\ldots)$ over an index range $100 \le k \le 200\text{,}$

\begin{equation*} 100+101+\cdots+200 = \sum_{k=100}^{200} k. \end{equation*}

Using the Summation as Net Accumulated Change theorem, we can write the summation as a difference

\begin{equation*} \sum_{k=100}^{200} k = \sum_{k=1}^{200} k - \sum_{k=1}^{99}. \end{equation*}

The two summations are accumulations from Theorem 3.4.9:

\begin{gather*} \sum_{k=1}^{200} k = \frac{200(201)}{2} = 20100, \\ \sum_{k=1}^{99} k = \frac{99(100)}{2} = 4950. \end{gather*}

Consequently,

\begin{equation*} \sum_{k=100}^{200} k = 20100 - 4950 = 15150. \end{equation*}

Subsection3.4.5Summations of Linear Combinations

The elementary summation formulas allow us to compute sums involving only the elementary terms. Combining these formulas using the properties of summation, namely using the constant multiple rule and the sum rule, we can compute sums of any linear combination of the elementary terms.

Example3.4.15

Find $\displaystyle \sum_{k=1}^{20} (500+60k-2k^2)\text{.}$

Solution

The increments in the sum consist of a constant ($500$), a constant multiple of the index ($60k$), and a constant multiple of the square of the index ($-2k^2$). The linearity property of summation 3.4.6 allows us to compute the sum using the elementary formulas. Although linearity allows the two steps to be done at once, the following illustrates the steps (sum and constant multiple rules) in order:

\begin{align*} \sum_{k=1}^{20} [500+60k-2k^2] &= \sum_{k=1}^{20} [500] + \sum_{k=1}^{20} [60k] + \sum_{k=1}^{20} [-2k^2] \\ &= \sum_{k=1}^{20} [500] + 60 \sum_{k=1}^{20} [k] -2 \sum_{k=1}^{20} [k^2]. \end{align*}

The brackets emphasize that the increments of a summation are given by a particular value or formula. Each of these summations involve elementary increment sequences for which we have explicit formulas.

\begin{gather*} \sum_{k=1}^{20} [500] = 500(20) = 10000, \\ \sum_{k=1}^{20} [k] = \frac{20(21)}{2} = 210, \\ \sum_{k=1}^{20} [k^2] = \frac{20(21)(41)}{6} = 2870. \end{gather*}

Consequently,

\begin{equation*} \sum_{k=1}^{20} [500+60k-2k^2] = 10000 + 60(210) - 2(2870) = 16860. \end{equation*}

The same strategy still applies if the constant multiple coefficients are written using parameters or even using variables other than the dummy index variable of summation. In particular, when the upper limit of the summation is a variable, the formula for the sequence might also involve that variable as well as the index variable. Because this will be encountered frequently, an example is provided below.

Example3.4.16

Find a formula for $\displaystyle \sum_{k=1}^{n} \left( \frac{3k}{n^2} - \frac{k^2}{n^3} \right)$ that involves only $n\text{.}$

Solution

The sequence of increments is $\displaystyle x_k = \frac{3k}{n^2} - \frac{k^2}{n^3}\text{.}$ We recognize this as a linear combination of the more elementary sequences $k$ and $k^2$ if we rewrite the sequence

\begin{equation*} x_k = \frac{3}{n^2} \cdot k + \frac{-1}{n^3} \cdot k^2. \end{equation*}

Because the coefficients of this linear combination only involve $n$ and not the dummy variable of the summation $k\text{,}$ we can rewrite the summation as a corresponding linear combination and then apply the elementary summation formulas to find our desired formula.

\begin{align*} \sum_{k=1}^{n} \left( \frac{3k}{n^2} - \frac{k^2}{n^3}\right) &= \frac{3}{n^2} \sum_{k=1}^{n} [k] - \frac{1}{n^3} \sum_{k=1}^{n}[k^2] \\ &= \frac{3}{n^2} \cdot \frac{n(n+1)}{2} - \frac{1}{n^3} \cdot \frac{n(n+1)(2n+1)}{6} \\ &= \frac{3n(n+1)}{2n^2} - \frac{n(n+1)(2n+1)}{6n^3}. \end{align*}

There are no convenient summation rules for products or quotients, with one exception. If the product can be rewritten as a sum using the distributive property of multiplication, then we can sometimes use linearity after this simplification in terms of elementary formulas. If the increments are not linear combinations of elementary terms, then we have no methods for simplifying the calculation.

Example3.4.17

Find a formula for $\displaystyle \sum_{k=1}^{n} (2-\frac{3k}{n})(1+\frac{2k}{n})$ that only involves $n\text{.}$

Solution

Use the distributive property (aka FOIL) to rewrite the product as a sum which can be identified as a linear combination of a constant term, $k\text{,}$ and $k^2\text{:}$

\begin{align*} (2-\frac{3k}{n})(1+\frac{2k}{n}) &= 2+\frac{4k}{n} - \frac{3k}{n} -\frac{12k^2}{n^2}\\ &= 2 + \frac{1}{n} \cdot k - \frac{12}{n^2} k^2. \end{align*}

The linearity property of summation 3.4.6 allows us to compute the sum as the same linear combination of the elementary accumulations:

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

To simplify the answer, we need to cancel common factors and then rewrite the expression with a common denominator.

\begin{align*} \sum_{k=1}^{n} (2-\frac{3k}{n})(1+\frac{2k}{n}) &= 2n + \frac{n+1}{2} - \frac{2(n+1)(2n+1)}{n} \\ &= \frac{(2n)(2n) + n(n+1)-4(n+1)(2n+1)}{2n} \\ &= \frac{4n^2 + n^2 + n - 8n^2 -12n -4}{2n} \\ &= \frac{-3n^2 - 11n -4}{2n} \end{align*}

Subsection3.4.6Summary

• Summation of terms is equivalent to an accumulation of those terms as increments.
• The Summation Splitting Property allows us to split a summation over an index range into the sum of two summations over adjacent ranges.
• Every summation can be computed as the accumulated change of the terms as increments. The Summation as Net Accumulated Change theorem states that if we know the accumulation sequence $u$ with increments $x\text{,}$ then
\begin{equation*} \sum_{k=m}^{n} x_k = u_n - u_{m-1}. \end{equation*}
• The linearity properties of summation (the constant multiple rule and the sum rule) allow us to break summations involving sums into simpler summations over the same index range.

• Elementary accumulation formulas:

Subsection3.4.7Exercises

The following collection of problems practice applying the properties of summation. Given the following information about the sequence $x$ and $y\text{,}$ compute the desired summations.

\begin{gather*} x_0 = 8 \qquad \sum_{k=1}^{10} x_k = 42 \qquad \sum_{k=0}^{20} x_k = 30 \\ y_{19} = 4 \qquad y_{20} = -8 \qquad \sum_{k=0}^{18} y_k = -4 \qquad \sum_{k=11}^{20} y_k = 5 \end{gather*}
1

$\displaystyle \sum_{k=0}^{10} 4x_k$

2

$\displaystyle \sum_{k=0}^{20} x_k+y_k$

3

$\displaystyle \sum_{k=11}^{20} 3x_k-2y_k$

Compute the following sums using the summation properties and the elementary summation formulas.

4

$\displaystyle \sum_{k=1}^{20} 3k$

5

$\displaystyle \sum_{k=1}^{30} 4k-100$

6

$\displaystyle \sum_{k=12}^{20} k^2$

7

$\displaystyle \sum_{k=1}^{n} (1+3k)(2-5k)$

8

$\displaystyle \sum_{k=0}^{6} 3^k$

9

$3+3^3+3^5+3^7+\cdot+3^{19}$

Hint: Rewrite as a summation that can use the geometric sum.

10

The sum of three-digit multiples of 5

11

The sum of three-digit perfect squares

12

$\displaystyle \sum_{k=1}^{n} \left(\frac{4}{n}-\frac{5k}{n^2}\right)$

13

$\displaystyle \sum_{k=1}^{n} \frac{3k^2}{n^3}$

14

$\displaystyle \sum_{k=1}^{n} \left(2+\frac{3k}{n}\right)^2 \cdot \frac{1}{n}$