This document covers a few mathematical constructs that appear very frequently when doing algorithmic analysis. We spend minimal time in class reviewing these concepts, so this document is intended to serve as a general reference guide and as a concept refresher. Please head to office hours if you have any follow-up questions.

We also have a few practice problems located at the bottom if you’re very rusty and want some practice.

This document was written by Michael Lee, Meredith Wu, & Brian Chan.

Summations Review

The summation (∑\sum) is a way of concisely expressing the sum of a series of related values. For example, suppose we wanted a concise way of writing 1+2+3+⋯+8+9+101 + 2 + 3 + \cdots + 8 + 9 + 10. We can do so like this:

∑i=110i \sum_{i=1}^{10} i

The “i=1i = 1” expression below the ∑\sum symbol is initializing a variable called ii which is initially set to 1. We then increase ii by one from that initial value up to and including the number at the top of the ∑\sum symbol. We then take each value of ii and substitute it to the expression to the right of the ∑\sum symbol, and add each of those expressions together.

Here is another example:

∑i=132+i2=(2+12)+(2+22)+(2+32)=3+6+11=20 \begin{aligned} \sum_{i=1}^3 2 + i^2 &= (2 + 1^2) + (2 + 2^2) + (2 + 3^2) \\ &= 3 + 6 + 11 \\ &= 20 \end{aligned}

More generally, the summation operation is defined as follows:

∑i=abf(i)=f(a)+f(a+1)+f(a+2)+⋯+f(b−2)+f(b−1)+f(b) \sum_{i=a}^b f(i) = f(a) + f(a + 1) + f(a + 2) + \cdots + f(b - 2) + f(b - 1) + f(b)

…where a,ba, b are integers such that a≤ba \leq b and f(x)f(x) is some arbitrary function.

One thing to note is that the bounds of a summation are inclusive: in the examples above, ii varies from aa up to and including bb.

We will see examples of summations in use when analyzing the behavior of loops later this quarter.

Useful Summation Identities

Splitting a Sum

Rule:

∑i=ab(x+y)=∑i=abx+∑i=aby\displaystyle \sum_{i=a}^b (x + y) = \sum_{i=a}^b x + \sum_{i=a}^b y

Example:

∑i=58i=5+6+7+8=∑i=08i−∑i=04i\displaystyle \sum_{i=5}^{8} i = 5 + 6 + 7 + 8 = \sum_{i=0}^{8} i - \sum_{i=0}^{4} i

Adjusting Summation Bounds

Rule:

∑i=abf(x)=∑i=0bf(x)−∑i=0a−1f(x)\displaystyle \sum_{i=a}^b f(x) = \sum_{i=0}^b f(x) - \sum_{i=0}^{a - 1} f(x)

Example:

∑i=58i=5+6+7+8=∑i=08i−∑i=04i\displaystyle \sum_{i=5}^{8} i = 5 + 6 + 7 + 8 = \sum_{i=0}^{8} i - \sum_{i=0}^{4} i

Factoring out a Constant

Rule:

∑i=abcf(i)=c∑i=abf(i)\displaystyle \sum_{i=a}^b cf(i) = c \sum_{i=a}^b f(i)

Example:

∑i=1510n=10∑i=15n\displaystyle \sum_{i=1}^5 10n = 10\sum_{i=1}^5 n

Summation of a Constant

Rule:

∑i=0n−1c=c+c+⋯+c⏟n times=cn\displaystyle \sum_{i=0}^{n-1} c = \underbrace{c + c + \cdots + c}_{\text{$n$ times}} = cn

Example:

∑i=05−110=10+10+10+10+10=50\displaystyle \sum_{i=0}^{5-1} 10 = 10 + 10 + 10 + 10 + 10 = 50

Gauss’s Identity

Rule:

∑i=0n−1i=n(n−1)2\displaystyle \sum_{i=0}^{n-1} i = \frac{n(n - 1)}{2}

Example:

∑i=010−1i=10(9)2=45\displaystyle \sum_{i=0}^{10-1} i = \frac{10(9)}{2} = 45

Sum of Squares

Rule:

∑i=0n−1i2=n(n−1)(2n−1)6\displaystyle \sum_{i=0}^{n-1} i^2 = \frac{n(n - 1)(2n - 1)}{6}

Example:

∑i=010−1i2=10⋅9⋅196=285\displaystyle \sum_{i=0}^{10-1} i^2 = \frac{10 \cdot 9 \cdot 19}{6} = 285

Finite Geometric Series

Rule:

(Applicable only when x≠1x \ne 1)

∑i=0n−1xi=xn−1x−1\displaystyle \sum_{i=0}^{n-1} x^i = \frac{x^n - 1}{x - 1}

Example:

∑i=010−15i=510−15−1=2441406\displaystyle \sum_{i=0}^{10 - 1} 5^i = \frac{5^{10} - 1}{5 - 1} = 2441406

Infinite Geometric Series

Rule:

(Applicable only when −1<x<1-1 \lt x \lt 1)

∑i=0∞xi=11−x\displaystyle \sum_{i=0}^\infty x^i = \frac{1}{1 - x}

Example:

∑i=0∞(12)i=11−1/2=2\displaystyle \sum_{i=0}^\infty \left(\frac{1}{2}\right)^i = \frac{1}{1 - 1/2} = 2

Practice Problems

  1. Simplify ∑k=1nk(k+1)\displaystyle \sum_{k=1}^n k(k + 1)
  2. Show that the sum of the first nn positive odd integers is n2n^2.
  3. Simplify ∑k=1n(n−k)\displaystyle \sum_{k=1}^n (n-k).
  4. Simplify ∑k=0n2k\displaystyle \sum_{k=0}^n 2^k.
  5. Show that ∑k=1∞12k\displaystyle \sum_{k=1}^{\infty} \frac{1}{2^k} converges to 1.
Solutions

Problem 1: Simplify ∑k=1nk(k+1)\displaystyle \sum_{k=1}^n k(k + 1)

∑k=1nk(k+1)=∑k=1nk2+k=n(n+1)(2n+1)6+n(n+1)2 \displaystyle \begin{aligned} \sum_{k=1}^n k(k+1) &= \sum_{k=1}^n k^2+k \\ &= \frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} \end{aligned}

Problem 2: Show that the sum of the first nn positive odd integers is n2n^2.

∑k=1n(2k−1)=2∑k=1nk−∑k=1n1=2n(n+1)2−n=n2 \displaystyle \begin{aligned} \sum_{k=1}^n (2k - 1) &= 2 \sum_{k=1}^n k - \sum_{k=1}^n 1\\ & = 2 \frac{n(n+1)}{2} - n \\ & = n^2 \end{aligned}

Problem 3: Simplify ∑k=1n(n−k)\displaystyle \sum_{k=1}^n (n-k).

∑k=1n(n−k)=(n−1)+(n−2)+(n−3)+...+0=1+2+...+(n−1)=∑k=1n−1k=n(n−1)2 \displaystyle \begin{aligned} \sum_{k=1}^n (n-k) &= (n-1) + (n-2) + (n-3) + ... + 0\\ &= 1 + 2 + ... + (n-1) \\ &= \sum_{k=1}^{n-1} k \\ &= \frac{n(n-1)}{2} \end{aligned}

Problem 4: Simplify ∑k=0n2k\displaystyle \sum_{k=0}^n 2^k.

∑k=0n2k=20+21+22+...+2n=1+2+4+...+2n=2n+1−12−1=2n+1−1 \displaystyle \begin{aligned} \sum_{k=0}^n 2^k &= 2^0 + 2^1 + 2^2 + ... + 2^n \\ &= 1 + 2 + 4 + ... + 2^n \\ &= \frac{2^{n+1} - 1}{2 - 1} \\ &= 2^{n+1} - 1 \end{aligned}

Problem 5: Show that ∑k=1∞12k\displaystyle \sum_{k=1}^{\infty} \frac{1}{2^k} converges to 1.

∑k=1∞12k=12+14+18+116...=∑k=0∞1212k=12∑k=0∞12k=12⋅11−12=1 \displaystyle \begin{aligned} \sum_{k=1}^{\infty} \frac{1}{2^k} &= \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} ...\\ &= \sum_{k=0}^{\infty} \frac{1}{2}\frac{1}{2^k}\\ &= \frac{1}{2} \sum_{k=0}^{\infty} \frac{1}{2^k}\\ &= \frac{1}{2} \cdot \frac{1}{1-\frac{1}{2}} \\ &= 1 \end{aligned}