Summations and sigma notation#
Table of Contents#
Finite Sum#
Given a sequence \(a_1, a_2, \dotsc, a_n\) of numbers where \(n\) is a nonnegative integer the finite sum \(a_1 + a_2 + \dotsb + a_n\) can be expressed as
\(\begin{aligned} \sum_{k = 1}^n a_k \end{aligned}\)
If \(n = 0\) then the summation is defined to be \(0\). The value of a finite series is always well-defined and the order in which its terms are added does not matter.
Infinite Sum#
Given an infinite sequence \(a_1, a_2, \dotsc\) of numbers the infinite sum \(a_1 + a_2 + \dotsb\) can be expressed as
\(\begin{aligned} \sum_{k = 1}^\infty a_k = \lim_{n \to \infty} \sum_{k = 1}^n a_k \end{aligned}\)
If the limit does not exist then the series diverges; otherwise, it converges. The terms of a convergent series cannot always be added in any order. However, the terms of an absolutely convergent series can be rearranged. (An absolutely convergent series \(\sum_{k = 1}^\infty a_k\) is a series for which the series \(\sum_{k = 1}^\infty |a_k|\) also converges.)
Linearity#
For any real number \(c\) and any finite sequences \(a_1, a_2, \dotsc, a_n\) and \(b_1, b_2, \dotsc, b_n\)
\(\begin{aligned} \sum_{k = 1}^n (c a_k + b_k) = c \sum_{k = 1}^n a_k + \sum_{k = 1}^n b_k \end{aligned}\)
\(\begin{aligned} \sum_{k = 1}^n \Theta(f(k)) = \Theta \left( \sum_{k = 1}^n f(k) \right) \end{aligned}\)
In this latter equation, the \(\Theta\)-notation on the left-hand side applies to the variable \(k\) but on the right-hand side it applies to the variable \(n\).
These linearity properties also holds for infinite convergent series.
Arithmetic Series#
The summation
\(\begin{aligned} \sum_{k = 1}^n k = 1 + 2 + \dotsb + n \end{aligned}\)
is an arithmetic series and has the value
\(\begin{aligned} \sum_{k = 1}^n k = \frac{n(n + 1)}{2} = \Theta(n^2) \end{aligned}\)
Gauss’ Proof
\( \begin{aligned} S &= 1 && + && 2 && + && \dotsb && + && n - 1 && + && n \\ S &= n && + && n - 1 && + && \dotsb && + && 2 && + && 1 \\ 2S &= (n + 1) && + && (n + 1) && + && \dotsb && + && (n + 1) && + && (n + 1) \\ &= n(n + 1) \\ S &= \frac{n(n + 1)}{2} \end {aligned} \)
\(\blacksquare\)
Proof by Mathematical Induction
\(n = 1 \implies \sum_{k = 1}^1 k = 1 = \frac{1 \times (1 + 1)}{2}\)
Assume that \(\sum_{k = 1}^n k = \frac{n(n + 1)}{2}\) up to \(n\) and show that it also holds for \(n + 1\).
\( \begin{aligned} \sum_{k = 1}^{n + 1} k = \left( \sum_{k = 1}^n k \right) + n + 1 = \frac{n(n + 1)}{2} + n + 1 = \frac{n(n + 1) + 2(n + 1)}{2} = \frac{(n + 1)((n + 1) + 1)}{2} \end {aligned} \)
\(\blacksquare\)
A general arithmetic series includes an additive constant \(a \ge 0\) and a constant coefficient \(b \gt 0\) in each term, but has the same total asymptotically.
\(\begin{aligned} \sum_{k = 1}^n (a + bk) = \Theta(n^2) \end{aligned}\)
Sum of Squares#
\(\begin{aligned} \sum_{k = 0}^n k^2 = \frac{n(n + 1)(2n + 1)}{6} \end{aligned}\)
On the one hand, the telescoping series
\( \begin{aligned} \sum_{k = 1}^n (k + 1)^3 - k^3 = (n + 1)^3 - 1 = n^3 + 3n^2 + 3n \end {aligned} \)
On the other hand,
\( \begin{aligned} \sum_{k = 1}^n (k + 1)^3 - k^3 &= \sum_{k = 1}^n (k + 1)(k^2 + 2k + 1) - k^3 = \sum_{k = 1}^n 3k^2 + 3k + 1 \\ &= 3 \sum_{k = 1}^n k^2 + 3 \sum_{k = 1}^n k + \sum_{k = 1}^n 1 \\ &= 3 \sum_{k = 1}^n k^2 + 3 \times \frac{n(n + 1)}{2} + n \\ &= 3S + \frac{3}{2} n^2 + \frac{3}{2} n + n \\ &= 3S + \frac{3}{2} n^2 + \frac{5}{2} n \\ \end {aligned} \)
And so
\( \begin{aligned} 3S + \frac{3}{2} n^2 + \frac{5}{2} n &= n^3 + 3n^2 + 3n \\ 3S &= n^3 + \frac{3}{2} n^2 + \frac{1}{2} n \\ 3S &= \frac{2n^3 + 3n^2 + n}{2} \\ S &= \frac{n(n + 1)(2n + 1)}{6} \\ \end {aligned} \)
Sum of Cubes#
\(\begin{aligned} \sum_{k = 0}^n k^3 = \left( \frac{n(n + 1)}{2} \right)^2 = \frac{n^2 (n + 1)^2}{4} \end{aligned}\)
Geometric Series#
For real \(x \ne 1\) the summation
\(\begin{aligned} \sum_{k = 0}^n x^k = 1 + x + x^2 + \dotsb + x^n \end{aligned}\)
is a geometric series and has the value
\(\begin{aligned} \sum_{k = 0}^n x^k = \frac{x^{n + 1} - 1}{x - 1} \end{aligned}\)
The infinite decreasing geometric series occurs when the summation is infinite and \(|x| \lt 1\)
\(\begin{aligned} \sum_{k = 0}^\infty x^k = \frac{1}{1 - x} \end{aligned}\)
If we assume that \(0^0 = 1\) these formulas apply even when \(x = 0\).
Integrating and differentiating formulas yield additional formulas. For example, differentiate the infinite decreasing geometric series and then multiply it by \(x\).
\( \begin{aligned} x \cdot \frac{d}{dx} \left( \sum_{k = 0}^\infty x^k \right) &= x \cdot \frac{d}{dx} \left( \frac{1}{1 - x} \right) \\ \sum_{k = 0}^\infty x \cdot \frac{d}{dx} (x^k) &= x \cdot \frac{d}{dx} \left( \frac{1}{1 - x} \right) \\ \sum_{k = 0}^\infty kx^k &= \frac{x}{(1 - x)^2} \\ \end {aligned} \)
And so we also have
\(\begin{aligned} \sum_{k = 0}^\infty kx^k = \frac{x}{(1 - x)^2} \end{aligned}\)
for \(|x| \lt 1\).
Harmonic Series#
For positive integers \(n\) the \(n\)-th harmonic number is
\(\begin{aligned} H_n = 1 + \frac{1}{2} + \frac{1}{3} + \dotsb + \frac{1}{n} = \sum_{k = 1}^n \frac{1}{k} = \ln n + O(1) \end{aligned}\)
\(\ln (n + 1) \le H_n \le \ln n + 1\)
Telescoping Series#
For any sequence \(a_0, a_1, \dotsc, a_n\)
\(\begin{aligned} \sum_{k = 1}^n (a_k - a_{k - 1}) = a_n - a_0 \end{aligned}\)
since each of the terms \(a_1, a_2, \dotsc, a_{n - 1}\) is added in exactly once and substracted out exactly once. We say that the sum telescopes.
Similarly
\(\begin{aligned} \sum_{k = 0}^{n - 1} (a_k - a_{k + 1}) = a_0 - a_n \end{aligned}\)
EXAMPLE
\( \begin{aligned} \sum_{k = 1}^{n - 1} \frac{1}{k(k + 1)} = \sum_{k = 1}^{n - 1} \left( \frac{1}{k} - \frac{1}{k + 1} \right) = 1 - \frac{1}{n} \end {aligned} \)
Re-indexing summations#
A series can sometimes be simplified by changing its index, often reversing the order of summation. Generally, if the summation index appears in the body of the sum with a minus sign, it’s worth thinking about re-indexing.
EXAMPLE
\( \begin{aligned} \sum_{k = 0}^n a_{n - k} = a_n + a_{n - 1} + \dotsb + a_1 + a_0 = a_0 + a_1 + \dotsb + a_{n - 1} + a_n = \sum_{j = 0}^n a_j && \text{where}\,\,\, j = n - k \end {aligned} \)
EXAMPLE
\( \begin{aligned} \sum_{k = 1}^n \frac{1}{n - k + 1} = \frac{1}{n} + \frac{1}{n - 1} + \dotsb + \frac{1}{2} + 1 = 1 + \frac{1}{2} + \dotsb + \frac{1}{n - 1} + \frac{1}{n} = \sum_{j = 1}^n \frac{1}{j} && \text{where}\,\,\, j = n - k + 1 \end {aligned} \)
Products#
The finite product \(a_1 a_2 \dotsm a_n\) can be expressed as
\(\begin{aligned} \prod_{k = 1}^n a_k \end{aligned}\)
If \(n = 0\) then the product is defined to be \(1\).
Converting between summations and products#
\( \begin{aligned} \lg \left( \prod_{k = 1}^n a_k \right) = \sum_{k = 1}^n \lg a_k \end {aligned} \)
Summations and asymptotic analysis#
Mathematical induction can be used to prove an upper or lower bound on a summation.
EXAMPLE
Prove the asymptotic upper bound \(\sum_{k = 0}^n 3^k = O(3^n)\). In other words, prove \(\sum_{k = 0}^n 3^k \le c3^n\) for some constant \(c\) for all sufficiently large \(n\).
Proof by Mathematical Induction
Basis: show that the bound holds for \(n = 0\).
\(n = 0 \implies \sum_{k = 0}^0 3^k = 1 \le c \cdot 1\) as long as \(c \ge 1\).
Assume that the bound holds for \(n\) and show that it also holds for \(n + 1\).
\( \begin{aligned} \sum_{k = 0}^{n + 1} 3^k = \left( \sum_{k = 0}^n 3^k \right) + 3^{n + 1} \le c3^n + 3^{n + 1} = \left( \frac{1}{3} + \frac{1}{c} \right) c3^{n + 1} \le c3^{n + 1} \end {aligned} \)
as long as \(\frac{1}{3} + \frac{1}{c} \le 1 \iff \frac{1}{c} \le \frac{2}{3} \iff c \ge \frac{3}{2}\)
\(\blacksquare\)
EXAMPLE
Prove the asymptotic upper bound \(\sum_{k = 1}^n k = O(n^2)\). In other words, prove \(\sum_{k = 1}^n k \le cn^2\) for some constant \(c\) for all sufficiently large \(n\).
Basis: show that the bound holds for \(n = 1\).
\(n = 1 \implies \sum_{k = 1}^1 k = 1 \le c \cdot 1^2\) as long as \(c \ge 1\).
Inductive step: assume that the bound holds for \(n\) and show that it also holds for \(n + 1\).
\( \begin{aligned} \sum_{k = 1}^{n + 1} k = \left( \sum_{k = 1}^n k \right) + n + 1 \le cn^2 + n + 1 \le cn^2 + n + 1 + ((c - 1)n + c(n + 1) - 1) = c(n + 1)^2 \end {aligned} \)
\( \begin{aligned} cn^2 + n + 1 + ((c - 1)n + c(n + 1) - 1) &= cn^2 + n + 1 + (cn - n + cn + c - 1) \\ &= cn^2 + n + 1 + 2cn - n + c - 1 \\ &= cn^2 + 2cn + c \\ &= c(n^2 + 2n + 1) \\ &= c(n + 1)^2 \\ \end {aligned} \)
Acknowledgments#
2022 Cormen, Leiserson, Rivest, & Stein. Introduction to Algorithms. 4e. MIT Press.
[ h ] 2020 Stewart, James. Calculus. 9e. Cengage.