Skip to main content
Contents Index Dark Mode Prev Up Next \(\newcommand{\im}{{\mathrm{im}}}
\newcommand{\given}{{\, :\,}}
\newcommand{\hanoi}{\mathrm{hanoi}}
\newcommand{\lcm}{{\mathrm{lcm}}}
\newcommand{\ID}{{\mathrm{ID}}}
\newcommand{\chr}{{\mathtt{chr}}}
\newcommand{\ord}{{\mathtt{ord}}}
\newcommand{\set}[1]{\left\lbrace #1 \right\rbrace}
\newcommand{\seq}[2]{( #1 )_{#2}}
\newcommand{\gr}[1]{\left( #1 \right)}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\size}[1]{\# #1}
\newcommand{\id}[1]{\mathrm{id}_{#1}}
\newcommand{\ip}[1]{\left\langle #1 \right\rangle}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceiling}[1]{\left\lceil #1\right\rceil}
\newcommand{\indemph}[1]{{\textbf{\emph{#1}}\index{#1}}}
\renewcommand{\implies}{\to}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\lxor}{\oplus}
\newcommand{\cP}{\wp}
\newcommand{\pset}{\cP}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\barr}[1]{\overline{#1}}
\newcommand{\sage}{\textsc{Sage}}
\newcommand{\magma}{\textsc{Magma}}
\newcommand{\bob}{\text{Bob}}
\newcommand{\true}{\text{T}}
\newcommand{\false}{\text{F}}
\newcommand{\ahat}{\hat{a}}
\newcommand{\ah}{\ahat}
\newcommand{\bhat}{\hat{b}}
\newcommand{\abar}{\bar{a}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\todo}[1]{{\color{red} TODO: #1}}
\renewcommand{\div}{\operatorname{div}}
\newcommand{\gexp}[3]{#1^{#2 #3}}
\newcommand{\gexpp}[3]{\displaystyle\left(#1\right)^{#2 #3}}
\newcommand{\glog}[3]{\log_{#1}^{#3}#2}
\def\dbend{{!!!}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Subsection 2.4.5 Summations
We now consider the addition of terms of a sequence.
Definition 2.4.5.1 .
Let \(\seq{a_n}{n}\) be a sequence of numbers. For a positive integer \(n\text{,}\) the sum from \(1\) to \(n\) of \(a_n\) , is
\begin{equation*}
\sum_{i = 1}^n a_i = a_1 + a_2 + \dots + a_n.
\end{equation*}
More generally, for \(m\leq n\text{,}\) we have
\begin{equation*}
\sum_{i = m}^n a_i = a_m + a_{m + 1} + \dots + a_n.
\end{equation*}
Even more generally, for a finite set \(I\text{,}\) we \({\sum_{i \in I} a_i}\) be the sum of the \(a_i\) with \(i\) in \(I\text{.}\)
Given a sequence
\(\seq{a_i}{i}\) as a function in Python
b, the following the function in
Listing 2.4.5.3 computes the sum from
\(m\) to
\(n\) of
\(\seq{a_i}{i}\text{.}\)
Listing 2.4.5.3. def summation(b,m,n):
"""
Input: function b, integers m,n in the domain of b
Return sum of b(i) for i from m to n.
"""
s = 0 # initialize sum
for i in range(m,n + 1):
s += a(i)
return s
Example 2.4.5.4 . Sum of squares.
\begin{equation*}
\sum_{i = 1}^3 i^2 = 1^2 + 2^2 + 3^2 = 14.
\end{equation*}
Theorem 2.4.5.5 .
Let \(\seq{a_n}{n}\) and \(\set{b_n}\) be defined on a finite set \(S\text{.}\) Suppose \(\sum_{i \in S} a_i\) and \(\sum_{i \in S} b_i\) exist. Then
\begin{equation*}
\sum_{i \in S} a_i + \sum_{i \in S} b_i = \sum_{i \in S} (a_i + b_i),
\end{equation*}
Proof.
With the associativity and commutativity of addition we get
\begin{align*}
\sum_{i=m}^n a_i + \sum_{i=m}^n b_i \amp =
\left(a_m + a_{m+1} + \dots + a_n\right)+ \left(b_m + b_{m+1} + \dots + b_n\right)\\
\amp=(a_m + b_m) + (a_{m+1} +b_{m+1}) + \dots + (a_n + b_n) \\
\amp= \sum_{i=m}^n (a_i + b_i)
\end{align*}
Theorem 2.4.5.6 .
Let \(\seq{a_n}{n}\) be defined on a finite set \(S\text{,}\) and let \(c\) be a real number. Suppose \(\sum_{i \in S} a_i\) exists. Then
\begin{equation*}
c\sum_{i \in S} a_i = \sum_{i \in S} ca_i.
\end{equation*}
Proof.
With the distributivity of multiplication over addition we get
\begin{align*}
c\cdot\sum_{i=m}^n a_i \amp= c\cdot\left(a_m + a_{m+1} + \dots + a_n\right) \\
\amp = (c\cdot a_m) + (c\cdot a_{m+1}) + \dots + (c\cdot a_n)\\
\amp =\sum_{i=m}^n (c\cdot a_i).
\end{align*}
We can use these properties to break down complicated sums into simpler ones.
Example 2.4.5.7 . Simplify a summation.
Break down the summation
\begin{equation*}
\sum_{k = 0}^{100} (3k^2 - 5 k + 2)
\end{equation*}
to a sum of simpler summations.
Solution .
\begin{align*}
\sum_{k = 0}^{100} (3k^2 - 5 k + 2) \amp = \sum_{k = 0}^{100} 3k^2 - \sum_{k = 0}^{100} 5 k +\sum_{k = 0}^{100} 2 \\
\amp = 3\sum_{k = 0}^{100} k^2 - 5\sum_{k = 0}^{100} k +2 \sum_{k = 0}^{100} 1.
\end{align*}
It remains to work out formulas for these summations:
\begin{equation*}
\sum_{k = 0}^{100} k^2, \quad
\sum_{k = 0}^{100} k, \quad \text{and} \quad \sum_{k = 0}^{100} 1,
\end{equation*}
Theorem 2.4.5.8 .
If \(a\) and \(r\) are real numbers with \(r \neq 0\text{,}\) then
\begin{equation*}
\sum_{i = 0}^n ar^i =
\begin{cases}
\frac{ar^{n + 1} - a}{r - 1} \amp \text{ if }r \neq 1,\\
(n + 1)a \amp \text{ if }r = 1.
\end{cases}
\end{equation*}
Proof.
If \(r = 1\text{,}\) then
\begin{equation*}
\sum_{i = 0}^n ar^i = \sum_{i = 0}^n a = \underbrace{a + a + \dots
+ a}_{n + 1\text{ times}} = (n + 1)a.
\end{equation*}
Now suppose \(r \neq 1\text{.}\) Let \(s = \sum_{i = 0}^n ar^i\text{.}\) Then
\begin{equation*}
rs = \sum_{i = 0}^n ar^{i + 1} = \sum_{i = 1}^{n + 1} ar^{i}.
\end{equation*}
Then
\begin{equation*}
s(r - 1) = rs - s = \sum_{i = 1}^{n + 1} ar^{i} - \sum_{i = 0}^n ar^i = ar^{n +
1} - a.
\end{equation*}
Dividing by \(r - 1\) gives the result.
Example 2.4.5.9 . Compute a sum.
Compute the sum
\begin{equation*}
1 + \frac{1}{2} + \frac{1}{2^2} + \dots + \frac{1}{2^{100}}.
\end{equation*}
Solution .
We rewrite the sum as
\begin{equation*}
1 + \left(\frac{1}{2}\right) + \left(\frac{1}{2}\right)^2 + \dots + \left(\frac{1}{2}\right)^{100}=
\sum_{i = 0}^{100}\left(\frac{1}{2}\right)^i.
\end{equation*}
This is the sum of a geometric progression with initial term
\(a = 1\) and common ratio
\(r = \frac{1}{2}\text{.}\) Using
Theorem 2.4.5.8 with
\(a = 1\text{,}\) \(r = \frac{1}{2}\text{,}\) and
\(n = 100\text{,}\) we have that the sum is equal to
\begin{equation*}
\frac{ar^{n + 1} - a}{r - 1} = \frac{\left(\frac{1}{2}\right)^{101} -
1}{\frac{1}{2} - 1} = 2\gr{1 - \frac{1}{2^{101}}},
\end{equation*}
which is just a bit less than \(2\text{.}\)
We revisit
Example 2.4.4.2 and derive a closed formula for the compound interest recurrence relation.
Example 2.4.5.10 . Compound interest closed formula.
Alice deposits
\(\$1000\) in an account that pays
\(5\%\) interest yearly and her grandmother transfers
\(\$100\) to the account every year right after the interest t has been paid.
The amount \(A_t\) in Alice’s account \(t\) years after her initial deposit is given by initial value
\begin{equation*}
A_0 = 1000
\end{equation*}
and the recurrence relation
\begin{equation*}
A_{t}=A_{t-1}+A_{t-1}\cdot 5\% +100=A_{t-1}\cdot 1.05+100.
\end{equation*}
Derive a closed formula for \(A_n\text{.}\)
Solution .
The first 3 terms of the sequence \(\seq{A_n}{n}\) are:
\begin{align*}
A_0 \amp =1000 \\
A_1 \amp =1000\cdot 1.05+100 \\
A_2 \amp =A_1\cdot 1.05+100 = (1000\cdot 1.05+100)\cdot 1.05+100 \\
\amp = 1000\cdot 1.05^2 +100\cdot 1.05+100 \\
A_3 \amp =A_2\cdot 1.05+100 \\
\amp = (1000\cdot 1.05^2 +100\cdot 1.05+100)\cdot 1.05+100 \\
\amp = 1000\cdot 1.05^3 +100\cdot 1.05^2+100\cdot 1.05+100
\end{align*}
For the general case we get:
\begin{align*}
A_n \amp = 1000\cdot 1.05^n+100\cdot 1.05^{n-1}+\dots+100\cdot 1.05+100 \\
\amp = 1000\cdot 1.05^n+100\cdot \sum_{i=0}^{n-1} 1.05^i
\end{align*}
Now we apply one of the summation formulae from Section
Section 2.4 to simplify our formula for
\(A_n\text{:}\)
\begin{align*}
A_n \amp = 1000\cdot 1.05^n+100\cdot \frac{1.05^n-1}{1.05-1} \\
\amp = 1000\cdot 1.05^n+100\cdot \frac{1.05^n-1}{0.05} \\
\amp = 1000\cdot 1.05^n+2000\cdot (1.05^n-1) \\
\amp = 3000\cdot 1.05^n-2000
\end{align*}
Before we prove the next formulas, we consider a special case.
Example 2.4.5.11 . Sum of natural numbers up to \(100\) .
Evaluate
\(\sum_{k= 1}^{100}k\)
Solution .
Let \(S=\sum_{k= 1}^{100}k\text{.}\) We write the summands of \(S\) twice in opposing order and then add the two sums summand by summand:
\begin{align*}
S \amp=\phantom{00}1+\phantom{00}2+\phantom{00}3+\dots+\phantom{0}98+\phantom{0}99+100\\
S \amp = 100+\phantom{0}99+\phantom{0}98+\dots+\phantom{00}3+\phantom{00}2+\phantom{00}1\\
2S\amp= \underbrace{101 + 101 + 101+\dots + 101+101+101}_{100\text{ copies of }101}=101\cdot 100
\end{align*}
Division by \(2\) yields
\begin{equation*}
\sum_{k= 1}^{100}k=S=\frac{101\cdot 100}{2}=5050.
\end{equation*}
Theorem 2.4.5.12 . Summation formulae.
Proof.
Example 2.4.5.13 . Sums from \(0\) to \(100\) .
\begin{equation*}
\sum_{k = 0}^{100} 1\text{ and }
\sum_{k = 0}^{100} k\text{ and }
\sum_{k = 0}^{100} k^2
\end{equation*}
Solution .
First, we compute
\(\sum_{k = 0}^{100} 1\text{.}\) We break off piece that starts at
\(k = 1\) so we can use
Theorem 2.4.5.12 , Finally,
\begin{equation*}
\sum_{k = 0}^{100} 1 = 1 + \sum_{k = 1}^{100} 1,
\end{equation*}
\begin{equation*}
\sum_{k = 0}^{100} 1 = 1 + 100 = 101.
\end{equation*}
Similarly, we write
\begin{equation*}
\sum_{k = 0}^{100} k = 0 + \sum_{k = 1}^{100} k.
\end{equation*}
\begin{equation*}
\sum_{k = 0}^{100} k = 0 + \frac{100(100 + 1)}{2} = {5050}.
\end{equation*}
Finally, we get
\begin{equation*}
\sum_{k = 0}^{100} k^2 = 0^2 + \sum_{k = 1}^{100} k^2.
\end{equation*}
Since \(0^2 = 0\text{,}\) this is just \(\sum_{k = 1}^{100} k^2\text{,}\) which matches the formula in the theorem using \(n = 100\text{.}\) Thus
\begin{equation*}
\sum_{k = 0}^{100} k^2 = 0 + \frac{100(100 + 1)(2(100) + 1)}{6} = {338350}.
\end{equation*}
Example 2.4.5.14 . Evaluation of a sum.
\begin{align*}
\sum_{k = 1}^{500} (7k + 3) \amp = 7\sum_{k = 1}^{500} k + \sum_{k = 1}^{500} 3 \\
\amp = 7 \cdot \frac{500(501)}{2} + 3(500) \\
\amp = {878250}.
\end{align*}
Example 2.4.5.15 . Evaluation of a sum.
Evaluate
\(\sum_{k=0}^{100}\left(4 \cdot k+7\right)\text{.}\)
Solution .
We have
\begin{align*}
\sum_{k=0}^{100}\left(4 \cdot k+7\right) \amp =\sum_{k=0}^{100}\left(4 \cdot k\right)+ \sum_{k=0}^{100} 7\\
\amp =\sum_{k=0}^{100}\left(4 \cdot k\right)+ 707\\
\amp =4\cdot\left(\sum_{k=1}^{100} k\right)+ 707\\
\amp =4\cdot\left(\sum_{k=0}^{100} k\right)+ 707\\
\amp =4\cdot\left(\frac{100\cdot(100+1)}{2}\right)+ 707\\
\amp =2\cdot 100\cdot(100+1) + 707\\
\amp =2\cdot 10100 + 707 = 20200+707=20907
\end{align*}
