Real Analysis: The Real Numbers
Summation
Finite Sums
Let $\{a_1, \ldots, a_m\}$ be a finite set of real numbers. Their sum $\sum : \mathbb{N}^{\mathbb{R}} \times \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{R}$ is a recursively defined function defined as follows:
$$\sum(a, p, q) = \left\{ \begin{array}{ll} 0 & q < p\\a(q) + \sum(a, p, q-1) & m \geq n\end{array} \right.$$
The symbol $\sum$ is the capital Greek letter sigma. The notation $\mathbb{N}^{\mathbb{R}}$ refers to the set of all real-valued functions of the natural numbers, i.e. the set of all real-valued sequences. Note that any finite set of real numbers of cardinality $q$ can be extended to a sequence that fits into this definition by setting all the elements past the $q$th one to $0.$
However, this notation is hopelessly awkward, and nobody uses it; it is only provided here for rigor. Just as sequences and finite sets are expressed with special sequence notation $a_n$ instead of standard function notation $a(n),$ so too are sums expressed with special summation notation:
$$\sum(a, p, q) = \sum\limits_{n=p}^{q} a_n$$
We can expand the sum to show a few of the individual terms, typically the first couple and the last:
$$\sum\limits_{n=p}^{q} a_n = a_p + a_{p+1} + \ldots + a_q$$
The variable $n$ is called the index variable of the sum, and the notation $n=p$ indicates that the sum start at index $p,$ and the superscript $q$ says that it should add all of the elements up until the $q$th element.
If we take $n=1,$ we see that the sum reduces to summing the first $m$ elements of a sequence:
$$\sum\limits_{n=1}^m a_n = a_1 + a_2 + \ldots + a_m.$$
However, per the definition, a sum need not start at 1 nor end at the final element in the set. For example, we may only choose to sum the elements indexed 4 through 6, like so:
$$\sum\limits_{i=4}^{6} = a_4 + a_5 + a_6.$$
The index variable need not be restricted to indexing into the set of numbers $\{a_1, \ldots, a_m\}$ and can be used algebraically in the sum. For example, the sum of the first $m$ positive numbers is given by the famous closed form solution:
$$\sum\limits_{n=1}^m i = 1 +2 + \ldots m = \dfrac{m(m+1)}{2}$$
Note that this notation corresponds to the implied definition of a sequence $\{a_n\}$ where $a_n = n.$ If a sequence $\{a_n\}$ is also used in the sum, for example $2^ia_i,$ this is shorthand for defining a sequence $\{b_n\}$ where $b_n = 2^na_n$ and summing over $\{b_n\}$ instead.
Multiplication and Summation
The distributive property generalizes from the product of one term with the sum of two terms to the product of one term to the sum of many terms:
$$\sum\limits_{n=p}^{q} ca_n = c\sum\limits_{n=1}^{m} a_n.$$
More intricate is how the product of two sums can be expressed compactly:
$$\left(\sum\limits_{n=p}^q a_n\right)\left(\sum\limits_{m=s}^t b_n\right) = \sum\limits_{n=p}^q \left(\sum\limits_{m=s}^t a_nb_m\right).$$
Summation by Parts
Given two finite sets of equal cardinality $\{a_1, \ldots, a_n\}$ and $\{b_1, \ldots, b_n\},$ we might want to ask what the sum of the products $\sum\limits_{n=p}^q a_nb_n$ for some indices $p, q \in [1, n].$ In order to develop a useful identity, we first define the concept of a partial sum, which is the sum of the first $k$ elements in an indexed finite set. Namely, the partial sum $s_k$ of a finite set $\{a_1, \ldots, a_n\}$ or infinite sequence $\{a_n\}$ is defined as
$$s_k = \sum\limits_{n=1}^{k} a_k.$$
Note that a partial sum is in fact no different from a regular sum. Instead, its meaning derives from the fact that it does not sum all of the numbers in the set.
Now for the identity in question. If $\{a_1, \ldots, a_m\}$ and $\{b_1, \ldots, b_m\}$ are finite sets, $\{s_1, \ldots, s_m\}$ form the partial sums of $\{a_1, \ldots, a_m\},$ and $ 1 \leq p < q \leq m,$ the following identity is called summation by parts:
$$\sum\limits_{n=p}^q a_nb_n = s_qb_q - s_{p-1}b_p + \sum\limits_{n=p}^{q-1}s_n(b_n - b_{n+1}).$$
As shown in the problems below, this identity is quite useful for proving closed form solutions to many sums. That is to say, we can prove that evaluating a potentially long and tedious sum is in fact equivalent to evaluating a much simpler expression with a fixed number of operations.
Problems
Compute the following sums:
-
$\sum\limits_{n=1}^4 n$
-
$\sum\limits_{n=1}^6 3n$
-
$\sum\limits_{n=1}^5 2^n$
-
$\sum\limits_{n=1}^4 n = 1 + 2 + 3 + 4 = 10$
-
$\sum\limits_{n=1}^6 3n = 3(1) + 3(2) + 3(3) + 4(3) = 30$
-
$\sum\limits_{n=1}^5 2^n = 2^1 + 2^2 + 2^3 + 2^4 + 2^5 = 2 + 4 + 8 + 16 + 32 = 62$
-
Show that $\sum\limits_{i=1}^n x_i \leq \sum\limits_{i=1}^n |x_i|$.
Proof by induction.
Base case: Note that $\sum\limits_{n=1}^1 x_n = x_1 \leq |x_1| = \sum\limits_{n=1}^1|x_n|$.
Inductive step: Assume $\sum\limits_{n=1}^m x_n \leq \sum\limits_{n=1}^m |x_n|$. Then
$ \sum\limits_{n=1}^{m+1} x_n = x_{m+1} + \sum\limits_{n=1}^m x_n \\ \sum\limits_{n=1}^{m+1} x_n \leq \left|x_{m+1} + \sum\limits_{n=1}^m x_n \right| \\ \sum\limits_{n=1}^{m+1} x_n \leq |x_{m+1}| + \left|\sum\limits_{n=1}^m x_n \right| \\ \sum\limits_{n=1}^{m+1} x_n \leq |x_{m+1}| + \sum\limits_{n=1}^m |x_n| \\ \sum\limits_{n=1}^{m+1} x_n \leq \sum\limits_{n=1}^{m+1} |x_n|$
The result follows by induction.
Show that $\sum\limits_{n=1}^{m} n = \dfrac{m(m+1)}{2}.$
Hint: Use induction.
Proof by induction.
Base case: If $m=1,$ then
$\dfrac{m(m+1)}{2} = \dfrac{1(1+1)}{2}\\\dfrac{m(m+1)}{2}= \dfrac{2}{2}\\\dfrac{m(m+1)}{2} = 1\\\dfrac{m(m+1)}{2} = \sum\limits_{n=1}^{1}n.$
Inductive step: Assume $\sum\limits_{n=1}^{m} n = \dfrac{m(m+1)}{2}.$ Then
$ \sum\limits_{n=1}^{m+1} n = (m+1) + \sum\limits_{n=1}^{m+1} n \\ \sum\limits_{n=1}^{m+1} n = (m+1) + \dfrac{m(m+1)}{2} \\ \sum\limits_{n=1}^{m+1} n = \dfrac{2(m+1)}{2} + \dfrac{m(m+1)}{2} \\ \sum\limits_{n=1}^{m+1} n = \dfrac{(m+1)(m+2)}{2} \\ $
The result follows by induction.
Product of Sums I: Show that $c\sum\limits_{n=1}^{m} a_n = \sum\limits_{n=1}^{n} ca_n.$
Hint: Use induction.
Proof by induction.
Base case: $c\sum\limits_{n=1}^{1} a_n = ca_1 = \sum\limits_{n=1}^{1}ca_n.$
Inductive step: Assume $c\sum\limits_{n=1}^{m}a_n = \sum\limits_{n=1}^{m}ca_n.$ Then
$ c\sum\limits_{n=1}^{m+1}a_n = c\left(a_{m+1} + \sum\limits_{n=1}^{m}a_n\right) \\ c\sum\limits_{n=1}^{m+1}a_n = ca_{m+1} + c\sum\limits_{n=1}^{m}a_n \\ c\sum\limits_{n=1}^{m+1}a_n = ca_{m+1} + \sum\limits_{n=1}^{m}ca_n \\ c\sum\limits_{n=1}^{m+1}a_n = \sum\limits_{n=1}^{m+1}ca_m $
The result follows by induction.
Product of Sums II: Show that $\left(\sum\limits_{i=1}^{n} a_i\right)\left(\sum\limits_{i=1}^{m} b_i\right) = \sum\limits_{i=1}^{n}\left(\sum\limits_{j=1}^{m} a_ib_j\right).$
Hint: Use induction.
Proof by induction. Base case:
$ \left(\sum\limits_{i=1}^1a_i\right)\left(\sum\limits_{j=1}^{m}b_j\right) = a_1\left(\sum\limits_{j=1}^{m}b_j\right)\\ \left(\sum\limits_{i=1}^1a_i\right)\left(\sum\limits_{j=1}^{m}b_j\right) = \left(\sum\limits_{j=1}^{m}a_1b_j\right)\\ \left(\sum\limits_{i=1}^1a_i\right)\left(\sum\limits_{j=1}^{m}b_j\right) = \sum\limits_{i=1}^1\left(\sum\limits_{j=1}^{m}a_ib_j\right)\\ $
Inductive step: Assume $\left(\sum\limits_{i=1}^{n}a_i\right)\left(\sum\limits_{j=1}^{m}b_j\right) = \sum\limits_{i=1}^{n}\left(\sum\limits_{j=1}^{m}a_ib_j\right).$ Then
$ \left(\sum\limits_{i=1}^{n+1}a_i\right)\left(\sum\limits_{j=1}^{m}b_j\right) = \left(a_{n+1} + \sum\limits_{i=1}^{n}a_i\right)\left(\sum\limits_{j=1}^{m}b_j\right) \\ \left(\sum\limits_{i=1}^{n+1}a_i\right)\left(\sum\limits_{j=1}^{m}b_j\right) = a_{n+1}\left(\sum\limits_{j=1}^{m}b_j\right) + \left(\sum\limits_{i=1}^{n}a_i\right)\left(\sum\limits_{j=1}^{m}b_j\right) \\ \left(\sum\limits_{i=1}^{n+1}a_i\right)\left(\sum\limits_{j=1}^{m}b_j\right) = \left(\sum\limits_{j=1}^{m}a_{n+1}b_j\right) + \sum\limits_{i=1}^{n}\left(\sum\limits_{j=1}^{m}a_ib_j\right) \\ \left(\sum\limits_{i=1}^{n+1}a_i\right)\left(\sum\limits_{j=1}^{m}b_j\right) = \sum\limits_{i=1}^{n+1}\left(\sum\limits_{j=1}^{m}a_ib_j\right) \\ $
The result follows by induction.
Summation by parts: Given real sequence $\{a_n\}$ and $\{b_n\}$ where $\{s_n\}$ is the sequence of partial sums of $\{a_n\},$ show that $\sum\limits_{n=p}^{q} a_nb_n = s_qb_q - s_{p-1}b_p + \sum\limits_{n=p}^{q-1} s_n(b_n - b_{n+1}).$
$\sum\limits_{n=p}^q a_nb_n = \sum\limits_{n=p}^{q} (s_n-s_{n-1})b_n \\ \sum\limits_{n=p}^q a_nb_n = \sum\limits_{n=p}^{q} s_nb_n - \sum\limits_{n=p}^{q}s_{n-1}b_n \\ \sum\limits_{n=p}^q a_nb_n = s_qb_q + \sum\limits_{n=p}^{q-1} s_nb_n - \sum\limits_{n=p}^{q}s_{n-1}b_n \\ \sum\limits_{n=p}^q a_nb_n = s_qb_q + \sum\limits_{n=p}^{q-1} s_nb_n - \sum\limits_{n=p-1}^{q-1}s_{n}b_{n+1} \\ \sum\limits_{n=p}^q a_nb_n = s_qb_q + \sum\limits_{n=p}^{q-1} s_nb_n - (s_{p-1}b_p + \sum\limits_{n=p}^{q-1}s_{n}b_{n+1}) \\ \sum\limits_{n=p}^q a_nb_n = s_qb_q - s_{p-1}b_p + \sum\limits_{n=p}^{q-1} s_nb_n - \sum\limits_{n=p}^{q-1}s_{n}b_{n+1} \\ \sum\limits_{n=p}^q a_nb_n = s_qb_q - s_{p-1}b_p + \sum\limits_{n=p}^{q-1} s_n(b_n - b_{n+1}) $