Summations you will reuse forever

The four sums that appear in almost every analysis

Running-time analysis is mostly counting, and counting collapses into a handful of summations. Memorize these closed forms — you will reach for them in insertion sort, merge sort, quicksort, heaps, and amortized analysis.

Arithmetic series. $$\sum_{k=1}^{n} k = \frac{n(n+1)}{2} = \Theta(n^2).$$ This is the cost of insertion sort's worst case (pass $i$ does up to $i$ comparisons, summed over passes).

Sum of squares. $$\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6} = \Theta(n^3).$$

Finite geometric series (for $x \ne 1$): $$\sum_{k=0}^{n} x^k = \frac{x^{n+1} - 1}{x - 1}.$$ When $|x| < 1$ the infinite tail converges: $\sum_{k=0}^{\infty} x^k = \frac{1}{1-x}$. Geometric series drive divide-and-conquer recurrences and amortized doubling.

Harmonic series. $$H_n = \sum_{k=1}^{n} \frac{1}{k} = \ln n + O(1),$$ tightly: $\ln(n+1) \le H_n \le \ln n + 1$, and $H_n \to \ln n + \gamma$ with Euler's constant $\gamma \approx 0.5772$. The harmonic series is *the* source of the $\lg n$ factor in randomized quicksort (Module 2).

Two manipulations worth knowing

Linearity: $\sum (c\,a_k + b_k) = c\sum a_k + \sum b_k$, and asymptotically $\sum \Theta(f(k)) = \Theta(\sum f(k))$ for monotone $f$.

Telescoping: $\sum_{k=1}^{n}(a_k - a_{k-1}) = a_n - a_0$ — every interior term cancels. For example $\sum_{k=1}^{n} \frac{1}{k(k+1)} = \sum (\frac{1}{k} - \frac{1}{k+1}) = 1 - \frac{1}{n+1}$.

When is a geometric *bound* valid? (the trap)

A standard way to bound a sum is: *if $a_{k+1}/a_k \le r$ for some constant $r < 1$, then $\sum_{k=0}^{n} a_k \le \frac{a_0}{1 - r}$* — the whole sum is $O(a_0)$, a constant times the first term.

The trap: ratio $< 1$ is not enough. You need ratio $\le r$ for a *fixed* $r$ strictly below 1. The harmonic series is the cautionary tale: its term ratio is $\frac{1/(k+1)}{1/k} = \frac{k}{k+1} < 1$ for every $k$ — yet $H_n$ diverges ($\to \infty$). The reason: that ratio creeps toward $1$ as $k$ grows, so no single $r < 1$ dominates it. Bounding $H_n$ by a geometric series gives a flatly wrong (finite) answer; the right tool is integral approximation: $H_n \le 1 + \int_1^n \frac{dx}{x} = 1 + \ln n$.

Worked example — verify a closed form empirically. Before trusting a closed form in a proof, sanity-check it on a concrete $n$. For $n = 100$: the loop $\sum_{k=1}^{100} k$ gives $5050$, and $\frac{100 \cdot 101}{2} = 5050$. For the geometric sum with $x=2, n=10$: the loop gives $2047$, and $\frac{2^{11} - 1}{2 - 1} = 2047$. The exercises below run exactly this check.