Section 4.4 Summation Formulas
¶Subsection 4.4.1 Overview
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.
Subsection 4.4.2 Summation 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
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
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:
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.
Theorem 4.4.1. Summation Splitting Property.
For any summation \(\displaystyle \sum_{i=m}^{n} x_i\) and intermediate index \(k\) with \(m \lt k \lt n\text{,}\) we can split the sum at \(k\) as
Proof.
The property is simply a generalization of the associative properties of addition. The basic idea is to group terms,
This splitting property allows us to rewrite a summation as a change in an associated accumulation sequence.
Theorem 4.4.2. Summation as Net Accumulated Change.
Given any sequence of terms \(x_k\) and an accumulation sequence \(u\) with \(\nabla u_k = x_k\text{,}\)
Proof.
The accumulation sequence can be written
By the Summation Splitting Property, if we split the sum at index \(k=m-1\text{,}\) we have
However, once we recognize
we have
Solving for the summation gives the stated conclusion,
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
Example 4.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.
The question is asking us to compute
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 4.3.12
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
and for the upper limit we have
Consequently, the sum of interest is
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),
Subsection 4.4.3 Algebraic 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.
Theorem 4.4.4. Constant Multiple Rule of Summation.
Let \(x\) be a sequence and \(\alpha\) a constant. Then for any lower and upper limits,
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.
Theorem 4.4.5. Sum Rule of Summation.
Let \(u\) and \(w\) be any two sequences defined for the range \(k=m,\ldots,n\text{.}\) Then
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.
Theorem 4.4.6. Linearity of Summation.
Let \(x\) and \(y\) be any two sequences with common domain and let \(\alpha\) and \(\beta\) be any two constants. Then for any lower and upper limits,
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.
Theorem 4.4.7. Difference Rule of Summation.
Let \(x\) and \(y\) be any two sequences with common domain. Then for any lower and upper limits,
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:
But the sum of the products gives a different result:
In general,
Subsection 4.4.4 Elementary 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 4.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{.}\)
Theorem 4.4.8. Sum of Constant Sequence.
Proof.
The accumulation sequence of interest is
The increment sequence \(x\) is a sequence of constants, \(c_k=c\text{.}\) The proposed explicit sequence is
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.
Since \((\nabla w)_n = c\) is the same increment as \(x_k\text{,}\) \(u\) and \(w\) are the same sequence.
Theorem 4.4.9. Sum of Natural Numbers.
Proof.
The accumulation sequence of interest is
The increment sequence \(x\) is defined by \(x_k=k\text{.}\) The proposed explicit sequence is
The initial values agree:
The increment for \(w\) is given by:
Since \((\nabla w)_n = n = x_n\text{,}\) \(u\) and \(w\) have the same increments and same initial value. By Theorem 4.3.3, \(u\) and \(w\) are equivalent.
Theorem 4.4.10. Sum of Squares.
Proof.
The accumulation sequence of interest is
so that increment sequence \(x\) is defined by \(x_k=k^2\text{.}\) The proposed explicit sequence is
The initial values agree:
The increment for \(w\) is given by:
Since \((\nabla w)_n = n^2 = x_n\text{,}\) \(u\) and \(w\) have the same increments and same initial value. By Theorem 4.3.3, \(u\) and \(w\) are equivalent.
Theorem 4.4.11. Sum of Cubes.
Proof.
The accumulation sequence of interest is
so that increment sequence \(x\) is defined by \(x_k=k^3\text{.}\) The proposed explicit sequence is
The initial values agree:
The increment for \(w\) is given by:
Since \((\nabla w)_n = n^3 = x_n\text{,}\) \(u\) and \(w\) have the same increments and same initial value. By Theorem 4.3.3, \(u\) and \(w\) are equivalent.
Theorem 4.4.12. Sum of a Geometric Sequence.
Proof.
The accumulation sequence of interest is
so that increment sequence \(x\) is defined by \(x_k=b^k\text{.}\) The proposed explicit sequence is
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
which matches the initial value of \(u\text{.}\) The increment for \(w\) is given by:
Since \((\nabla w)_n = b^n = x_n\text{,}\) \(u\) and \(w\) have the same increments and same initial value. By Theorem 4.3.3, \(u\) and \(w\) are equivalent.
Our first examples consider sums involving just the elementary terms.
Example 4.4.13.
Find the sum of the integers \(1, 2, \ldots, 100\text{.}\)
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:
Theorem Theorem 4.4.9 applies directly with \(n=100\text{,}\) so we know
Example 4.4.14.
Find the sum of the integers \(100, 101, \ldots, 200\text{.}\)
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{,}\)
Using the Summation as Net Accumulated Change theorem, we can write the summation as a difference
The two summations are accumulations from Theorem 4.4.9:
Consequently,
Subsection 4.4.5 Summations 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.
Example 4.4.15.
Find \(\displaystyle \sum_{k=1}^{20} (500+60k-2k^2)\text{.}\)
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 4.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:
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.
Consequently,
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.
Example 4.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{.}\)
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
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.
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.
Example 4.4.17.
Find a formula for \(\displaystyle \sum_{k=1}^{n} (2-\frac{3k}{n})(1+\frac{2k}{n})\) that only involves \(n\text{.}\)
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{:}\)
The linearity property of summation 4.4.6 allows us to compute the sum as the same linear combination of the elementary accumulations:
To simplify the answer, we need to cancel common factors and then rewrite the expression with a common denominator.
Subsection 4.4.6 Summary
- 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.
- Constant Multiple Rule of Summation: \(\displaystyle \sum_{k=m}^{n} \alpha x_k = \alpha \sum_{k=m}^{n} x_k\)
- Sum Rule of Summation: \(\displaystyle \sum_{k=m}^{n} [u_k+w_k] = \sum_{k=m}^{n} u_k + \sum_{k=m}^{n} w_k\)
- Linearity of Summation: \(\displaystyle \sum_{k=m}^{n} [\alpha u_k + \beta w_k] = \alpha \sum_{k=m}^{n} u_k +\beta \sum_{k=m}^{n} w_k\)
-
Elementary accumulation formulas:
- Sum of Constant Sequence: \(\displaystyle \sum_{k=1}^{n} c = cn\)
- Sum of Natural Numbers: \(\displaystyle \sum_{k=1}^{n} k = \frac{n(n+1)}{2}\)
- Sum of Squares: \(\displaystyle \sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\)
- Sum of Cubes: \(\displaystyle \sum_{k=1}^{n} k^3 = \frac{n^2(n+1)^2}{4}\)
- Sum of a Geometric Sequence: \(\displaystyle \sum_{k=0}^{n} b^k = \frac{b^{n+1}-1}{b-1}\)
Exercises 4.4.7 Exercises
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.
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}\)