Summation Formulas and Series

Why Summations Are the Currency of Algorithm Analysis

Almost every running-time analysis you will write in this book ends with a summation. The reason is structural: a loop that runs $n$ times and does $f(i)$ work on iteration $i$ costs exactly $\sum_{i=1}^{n} f(i)$ primitive operations. Nested loops produce nested sums. Recursive calls unfolded into a recursion tree produce a sum over levels. Amortized analyses produce sums of credit. The whole subject of analysis of algorithms is, at one level, the systematic study of which sums can be replaced by closed forms — expressions you can evaluate in $O(1)$ arithmetic ops instead of $O(n)$.

Consider the simplest possible non-trivial loop:

1total = 0
2for i in range(1, n + 1):
3    total += i
4return total

The cost (counting the addition as one unit) is $n$ operations, and the output the loop computes is $\sum_{i=1}^{n} i$. Both halves of that sentence are summations. The cost summation gives us the running time; the value summation gives us a closed form — $n(n+1)/2$ — that lets us replace the entire loop with a single arithmetic expression. Knowing summation identities is what lets you collapse $O(n)$ code into $O(1)$ code, and what lets you simplify a four-page running-time derivation into a two-line statement.

Working slogan. Loops produce sums. Recursion produces sums. Probabilistic analyses produce sums. Master a dozen summation identities and you have already mastered most of the algebra you will do in this book.

Sigma Notation: A Compact Vocabulary

The capital sigma notation packs a loop into one symbol. The expression

$\sum_{i=1}^{n} a_i = a_1 + a_2 + a_3 + \cdots + a_n$

has four moving parts: the index $i$, the lower bound 1, the upper bound $n$, and the body $a_i$. The bounds are inclusive on both ends: the sum has exactly $n - 1 + 1 = n$ terms when the index runs from 1 to $n$.

Three identities do almost all of the algebraic work you will ever do with sigma notation:

• Linearity. $\sum_{i=1}^{n} (\alpha\, a_i + \beta\, b_i) = \alpha \sum_{i=1}^{n} a_i + \beta \sum_{i=1}^{n} b_i$ for any constants $\alpha, \beta$. Constants slide out of sums; sums of sums split.
• Splitting at an index. $\sum_{i=1}^{n} a_i = \sum_{i=1}^{m} a_i + \sum_{i=m+1}^{n} a_i$ for any $1 \leq m < n$. Useful for recursion tree analyses where different levels behave differently.
• Reindexing. $\sum_{i=1}^{n} a_i = \sum_{j=0}^{n-1} a_{j+1}$ (shift by 1), or more generally $\sum_{i=a}^{b} f(i) = \sum_{j=0}^{b-a} f(j+a)$. This is the "rename the loop variable" identity.

The Arithmetic Series: Gauss's Trick

Legend: in the 1780s, a German schoolmaster tried to keep a class of ten-year-olds quiet by asking them to add the integers from 1 to 100. Carl Friedrich Gauss handed in the answer in seconds: $5050$. He had spotted that the sum could be paired up:

$\begin{aligned} S &= 1 + 2 + 3 + \cdots + 99 + 100 \\ S &= 100 + 99 + 98 + \cdots + 2 + 1 \\ 2S &= 101 + 101 + 101 + \cdots + 101 \quad (\text{100 copies}) \\ 2S &= 100 \cdot 101 \\ S &= \frac{100 \cdot 101}{2} = 5050. \end{aligned}$

The same pairing works for any $n$:

$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}.$

This is the most-used closed form in algorithm analysis. It appears every time a nested loop has the shape for i in range(n): for j in range(i):, because the inner loop runs $0 + 1 + 2 + \cdots + (n-1) = n(n-1)/2$ times in total. Any time you see a half-triangle of work, you should instantly think $\Theta(n^2)$.

A second proof: induction

Pairing is satisfying but only a sketch. Induction makes the same identity airtight. Base. For $n = 1$: LHS $= 1$, RHS $= 1 \cdot 2 / 2 = 1$. Step. Assume $\sum_{i=1}^{n} i = n(n+1)/2$. Then

$\sum_{i=1}^{n+1} i = \frac{n(n+1)}{2} + (n+1) = (n+1) \cdot \frac{n + 2}{2} = \frac{(n+1)(n+2)}{2},$

which is the formula with $n$ replaced by $n+1$. QED.

Sum of Squares, Sum of Cubes, and Faulhaber

For squared and cubed indices the closed forms are:

• $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$
• $\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2 = \left(\sum_{i=1}^{n} i\right)^2$

That last identity — the sum of cubes equals the square of the sum — is one of the small miracles of elementary number theory. It is also genuinely useful: it converts a cubic-looking nested-loop bound into a clean square.

Deriving the sum of squares by telescoping

A beautiful trick: take the algebraic identity $(i+1)^3 - i^3 = 3 i^2 + 3 i + 1$ and sum both sides from $i = 1$ to $n$. The left side telescopes (almost everything cancels):

$\sum_{i=1}^{n} \left[ (i+1)^3 - i^3 \right] = (n+1)^3 - 1.$

The right side, by linearity of $\sum$, equals $3 \sum i^2 + 3 \sum i + n$. We already know $\sum i = n(n+1)/2$. Plug in and solve for $\sum i^2$ and out pops the formula. A five-line proof for an identity that, written out, looks intimidating.

The general pattern: Faulhaber

The pattern continues: $\sum_{i=1}^{n} i^k$ is always a polynomial of degree $k+1$ in $n$, with leading term $\frac{n^{k+1}}{k+1}$. Faulhaber's 17th century formula gives the explicit polynomial. For algorithm analysis, the only fact you usually need is the asymptotic statement:

$\sum_{i=1}^{n} i^k = \Theta(n^{k+1}) \qquad \text{for any fixed } k \geq 0.$

The Geometric Series: Three Regimes

After the arithmetic series, the geometric series is the second load-bearing identity in algorithms. For any $r \neq 1$:

$\sum_{i=0}^{n-1} r^i = 1 + r + r^2 + \cdots + r^{n-1} = \frac{1 - r^n}{1 - r} = \frac{r^n - 1}{r - 1}.$

Proof. Let $S = 1 + r + r^2 + \cdots + r^{n-1}$. Then $r S = r + r^2 + \cdots + r^n$. Subtract: $(r - 1) S = r^n - 1$. Divide. Two lines.

The behavior of this series splits sharply into three regimes, and which regime you are in dominates the asymptotic class:

The decreasing case is the source of one of the most counterintuitive results in algorithm design: a sum with infinitely many positive terms can still be a constant. $1 + 1/2 + 1/4 + 1/8 + \cdots = 2$ is the canonical example. This is what makes amortized analysis of dynamic-array doubling work: copying happens infinitely often as the array grows, but the total copy cost over $n$ appends is bounded by a constant times $n$, because the sequence of resize costs is geometric.

The Harmonic Series and the Logarithm Hidden Inside

The harmonic numbers are the partial sums

$H_n = \sum_{i=1}^{n} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}.$

Unlike the previous sums, $H_n$ has no clean closed form in elementary functions. But its asymptotic behavior is known with great precision:

$H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12 n^2} + O\!\left(\frac{1}{n^4}\right),$

where $\gamma \approx 0.5772156649\ldots$ is the Euler-Mascheroni constant. For algorithm analysis the only thing that usually matters is the leading-order statement:

$H_n = \Theta(\log n).$

Why is the harmonic sum logarithmic? The integral argument

The continuous analogue of the discrete sum $\sum_{i=1}^{n} 1/i$ is the integral $\int_1^n \frac{1}{x} \, dx = \ln n$. Because $1/x$ is decreasing, the staircase of rectangles of height $1/i$ sandwiches the area under the curve from both sides. We get the two-sided bound

$\ln(n+1) \;\leq\; H_n \;\leq\; 1 + \ln n,$

which already gives $H_n = \Theta(\log n)$ with no further work.

Where the harmonic sum hides in algorithms

• Quicksort average case. The expected number of comparisons satisfies a recurrence whose solution involves $H_n$; that is exactly why average-case quicksort is $\Theta(n \log n)$, not $\Theta(n)$.
• Coupon collector. The expected number of trials to collect all $n$ coupons is $n H_n \approx n \ln n$. Used in load-balancer analysis, randomized algorithms, hashing.
• Hash chains. Expected length of the longest chain in a hash table with $n$ keys and $n$ buckets is $\Theta(\log n / \log \log n)$ — an analysis that uses harmonic-sum bounds.
• DCG ranking metric. Search engines and recommenders discount the $i$-th rank by $1/\log_2(i+1)$. Total ideal-DCG sums to a harmonic-like quantity.
• Disk seek scheduling, skip lists, treaps. Many analyses end with $H_n$ and conclude $O(\log n)$.

Telescoping Sums

A telescoping sum is a sum whose body can be written as $f(i+1) - f(i)$. When summed, all interior terms cancel:

$\sum_{i=1}^{n} \bigl[ f(i+1) - f(i) \bigr] = f(n+1) - f(1).$

We already used this once (for the sum of squares). It is the discrete analogue of the fundamental theorem of calculus, and it is the cleanest way to evaluate a sum without guessing an answer first.

Worked example: a small partial-fraction telescope

Compute $S = \sum_{i=1}^{n} \frac{1}{i(i+1)}$. Partial fractions: $\frac{1}{i(i+1)} = \frac{1}{i} - \frac{1}{i+1}$. So

$S = \sum_{i=1}^{n} \left( \frac{1}{i} - \frac{1}{i+1} \right) = 1 - \frac{1}{n+1} = \frac{n}{n+1}.$

Three lines, no induction, exact closed form. Telescoping is the algebra-level shortcut you should reach for whenever you see a difference structure.

Bounding Sums by Integrals

When no closed form exists, you can still pin down the asymptotic class of a sum by bounding it above and below with integrals. For a monotone function $f$ on $[1, n]$:

If $f$ is increasing, $\int_0^n f(x) \, dx \;\leq\; \sum_{i=1}^{n} f(i) \;\leq\; \int_1^{n+1} f(x) \, dx.$ If $f$ is decreasing, the inequalities flip:

$\int_1^{n+1} f(x) \, dx \;\leq\; \sum_{i=1}^{n} f(i) \;\leq\; f(1) + \int_1^n f(x) \, dx.$

This is, hands down, the most useful technique for asymptotic bounds when you cannot find a closed form. Examples:

• $\sum_{i=1}^{n} \log i \;\approx\; \int_1^n \log x \, dx = n \log n - n + 1 = \Theta(n \log n)$. That single line is the analysis of comparison-sort lower bounds and of $\log(n!)$ (Stirling).
• $\sum_{i=1}^{n} \sqrt{i} \;\approx\; \int_1^n \sqrt{x} \, dx = \tfrac{2}{3}(n^{3/2} - 1) = \Theta(n^{3/2})$.
• $\sum_{i=1}^{n} \frac{1}{i^2}$ is bounded by $1 + \int_1^\infty \frac{dx}{x^2} = 2$ — constant! In fact it converges to $\pi^2/6$ (the Basel problem).

Interactive: The Summation Estimator

Pick a summation type, slide $n$, and watch the amber staircase (the brute-force loop's running cumulative total) meet the blue dashed curve (the closed-form formula evaluated at the same $n$). They land at the same point because the closed form is, by construction, equal to the loop — just evaluable in $O(1)$ instead of $O(n)$ arithmetic.

Things to notice as you flip between the choices:

• Σ i grows like a parabola; the staircase hugs the quadratic curve.
• Σ 2^i shoots straight up: only the last bar matters — this is the "dominant-term rule" for increasing geometric series, visible to the eye.
• Σ (1/2)^i levels off at 2. You can crank $n$ to 100 and it stays bounded — that is what $\Theta(1)$ looks like for an infinite sum.
• Σ 1/i grows but very slowly. The shape is $\ln n$, just shifted up by $\gamma$.

Closed Form vs. Loop, in Two Languages

When you have a closed form, evaluating it is $O(1)$ — a handful of arithmetic operations no matter how big $n$ is. The loop version is $O(n)$. For $n = 10^9$, that is the difference between a nanosecond and a second. Below we compute three sums both ways and assert they agree.

Python: side-by-side closed form vs. loop

closed_form_vs_loop(20) returns six numbers plus six timings.

n = 20: starts at 0, ends at 210.

n = 20 iterates i over 1, 2, ..., 20 — twenty additions.

After i = 5: arith_loop = 1+2+3+4+5 = 15. Verify: 5·6/2 = 15. ✓

n = 20: 20 · 21 / 2 = 420 / 2 = 210. Three ops total.

n = 20: 210 == 210 ✓.

Iteration sequence of p: 1, 2, 4, 8, 16, ...

n = 20 after iter 1: geom_loop = 1. After iter 2: 3. After iter 3: 7. After iter 20: 1,048,575.

After iter 1: p = 2. After iter 2: p = 4. After iter 20: p = 2^20 = 1,048,576.

n = 20: 1 << 20 = 1,048,576. Minus 1: 1,048,575. Same as the loop.

n = 20 after iter 1: harm_loop = 1.0. After iter 2: 1.5. After iter 20: ~3.5977.

n = 20: ln(20) ≈ 2.9957, plus γ ≈ 0.5772 = 3.5729. True H_20 ≈ 3.5977. Gap ≈ 0.0248 ≈ 1/(2·20) ✓.

1import math
2import time
3
4def closed_form_vs_loop(n: int) -> dict:
5    """Compute three classical sums by both brute-force loop and closed form,
6    assert exact agreement, and time both methods."""
7    # --- Arithmetic sum: 1 + 2 + ... + n ---
8    t0 = time.perf_counter()
9    arith_loop = 0
10    for i in range(1, n + 1):
11        arith_loop += i
12    t1 = time.perf_counter()
13    arith_closed = n * (n + 1) // 2
14    t2 = time.perf_counter()
15    assert arith_loop == arith_closed
16
17    # --- Geometric sum: 1 + 2 + 4 + ... + 2^(n-1)  (r = 2) ---
18    t3 = time.perf_counter()
19    geom_loop = 0
20    p = 1
21    for _ in range(n):
22        geom_loop += p
23        p *= 2
24    t4 = time.perf_counter()
25    geom_closed = (1 << n) - 1     # 2**n - 1
26    t5 = time.perf_counter()
27    assert geom_loop == geom_closed
28
29    # --- Harmonic sum: 1 + 1/2 + 1/3 + ... + 1/n ---
30    t6 = time.perf_counter()
31    harm_loop = 0.0
32    for i in range(1, n + 1):
33        harm_loop += 1.0 / i
34    t7 = time.perf_counter()
35    harm_approx = math.log(n) + 0.5772156649  # Euler-Mascheroni constant
36    t8 = time.perf_counter()
37
38    return {
39        "n": n,
40        "arith":    {"loop": arith_loop, "closed": arith_closed,
41                     "loop_us": (t1 - t0) * 1e6, "closed_us": (t2 - t1) * 1e6},
42        "geometric":{"loop": geom_loop,  "closed": geom_closed,
43                     "loop_us": (t4 - t3) * 1e6, "closed_us": (t5 - t4) * 1e6},
44        "harmonic": {"loop": harm_loop,  "approx": harm_approx,
45                     "loop_us": (t7 - t6) * 1e6, "approx_us": (t8 - t7) * 1e6},
46    }
47
48print(closed_form_vs_loop(20))
49# n=20: arith_loop=210, arith_closed=210
50#       geom_loop=1048575, geom_closed=1048575 (= 2^20 - 1)
51#       harm_loop=3.5977..., ln(20)+gamma=3.5728  (gap shrinks like 1/(2n))

TypeScript: same identities, BigInt where needed

The same idea in TypeScript — the closed-form path stays $O(1)$; only the loop scales with $n$. We switch to BigInt for the geometric sum because 2^n overflows JS's 2⁵³ safe-integer range past $n = 53$.

n = 20: 0 → 1 → 3 → 6 → 10 → ... → 210.

n = 20: 20 * 21 / 2 = 210. Exact.

After iter 60: p = 2^60 = 1152921504606846976n.

n = 20: (1n << 20n) - 1n = 1048575n. Same as the loop.

n = 20: harmLoop ≈ 3.5977396571.

n = 20: Math.log(20) + 0.5772 ≈ 3.5729. Gap to true value ≈ 0.0248 ≈ 1/(2 · 20).

1function summationDemo(n: number) {
2  // ---- Arithmetic ----
3  let arithLoop = 0;
4  for (let i = 1; i <= n; i++) arithLoop += i;
5  const arithClosed = (n * (n + 1)) / 2;
6
7  // ---- Geometric (r = 2) using BigInt to stay exact ----
8  let geomLoop = 0n;
9  let p = 1n;
10  for (let i = 0; i < n; i++) { geomLoop += p; p *= 2n; }
11  const geomClosed = (1n << BigInt(n)) - 1n;
12
13  // ---- Harmonic ----
14  let harmLoop = 0;
15  for (let i = 1; i <= n; i++) harmLoop += 1 / i;
16  const harmApprox = Math.log(n) + 0.5772156649;  // Euler-Mascheroni
17
18  return {
19    arith:     { loop: arithLoop, closed: arithClosed,
20                 ok: arithLoop === arithClosed },
21    geometric: { loop: geomLoop,  closed: geomClosed,
22                 ok: geomLoop === geomClosed },
23    harmonic:  { loop: harmLoop,  approx: harmApprox,
24                 gap: Math.abs(harmLoop - harmApprox) },
25  };
26}
27
28console.log(summationDemo(20));
29// arith.ok    = true  (210 === 210)
30// geometric.ok = true (1048575n === 1048575n)
31// harmonic.gap ≈ 0.0248 (matches 1/(2n) = 0.025)

Three Worked Algorithm-Cost Calculations

Time to apply the machinery. Three classical algorithms, three different summations, three sharply different asymptotic conclusions.

1. Insertion sort: an arithmetic-series argument for Θ(n²)

Insertion sort, in its worst case, scans backwards through the sorted prefix to find the right slot for the next element. Iteration $i$ (with $i$ from $1$ to $n - 1$) does up to $i$ comparisons. Total worst-case comparison count:

$T(n) = \sum_{i=1}^{n-1} i = \frac{(n-1)n}{2} = \Theta(n^2).$

Two lines, no hand-waving. The arithmetic-series identity converted a loop count into a clean asymptotic. Insertion sort is $\Theta(n^2)$ in the worst case — a fact that justifies why merge sort, quicksort, and heapsort exist.

2. Building a heap: top-down vs. bottom-up

A binary heap of $n$ elements can be built two ways. The naive way: insert elements one at a time, each insertion sifting up at most $\log i$ levels:

$T_{\text{top}}(n) = \sum_{i=1}^{n} \log i = \log(n!) = \Theta(n \log n).$

We used the integral bound $\sum \log i \approx \int \log x \, dx = n \log n - n + 1$ (or equivalently Stirling's formula for $\log(n!)$).

The clever way (Floyd's heap construction): start from the bottom and sift down. A node at height $h$ does at most $h$ work, and there are about $n / 2^{h+1}$ nodes at height $h$. Total work:

$T_{\text{bot}}(n) = \sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot h = \frac{n}{2} \sum_{h=0}^{\log n} \frac{h}{2^h}.$

The inner sum is bounded by the closed form $\sum_{h=0}^{\infty} \frac{h}{2^h} = 2$ (a standard arithmetico-geometric series — differentiate the geometric formula). So $T_{\text{bot}}(n) \leq \frac{n}{2} \cdot 2 = n = \Theta(n)$. We just turned an $O(n \log n)$ algorithm into an $O(n)$ algorithm by reordering the work and invoking a bounded geometric-like series. This is the actual reason heapify in the standard library uses bottom-up.

3. Tower of Hanoi: a geometric series for 2ⁿ − 1

Tower of Hanoi with $n$ disks satisfies the recurrence $T(n) = 2 T(n-1) + 1$ with $T(1) = 1$. Unfolding:

$\begin{aligned} T(n) &= 2 T(n-1) + 1 \\ &= 2(2 T(n-2) + 1) + 1 = 4 T(n-2) + 2 + 1 \\ &= 8 T(n-3) + 4 + 2 + 1 \\ &\ \vdots \\ &= 2^{n-1} T(1) + 2^{n-2} + 2^{n-3} + \cdots + 1 \\ &= \sum_{i=0}^{n-1} 2^i = 2^n - 1. \end{aligned}$

The geometric-series identity took us from a recurrence to a closed form in one line. $T(n) = 2^n - 1$ is exact, not asymptotic — for 64 disks the famous answer is $2^{64} - 1 \approx 1.8 \times 10^{19}$ moves. The same technique handles $T(n) = 2 T(n/2) + n$ (merge sort: gives $\Theta(n \log n)$) and any divide-and-conquer recurrence in the Master Theorem family.

Where These Sums Show Up in Real Systems

These are not classroom curiosities. Each summation identity is doing work in production code right now.

Notice how often the same three or four series — arithmetic, geometric, harmonic, and their integrals — reappear. The world of algorithms is mostly built out of a small toolkit; you are not learning a list of formulas, you are learning the few that the rest of the field actually uses.

Pitfalls and Sanity Checks

A short list of mistakes that everyone makes once. The point is to make them once and never again.

• Off-by-one in the bounds. $\sum_{i=0}^{n}$ has $n+1$ terms, not $n$. $\sum_{i=1}^{n} 1 = n$, but $\sum_{i=0}^{n} 1 = n+1$. Always count by subtracting endpoints and adding one.
• Forgetting to multiply a constant by $n$. $\sum_{i=1}^{n} c = c n$, not $c$. Easy to drop in the middle of a longer derivation.
• Confusing geometric with arithmetic. $\sum 2 i$ is arithmetic (linear terms, $\Theta(n^2)$); $\sum 2^i$ is geometric (exponential terms, $\Theta(2^n)$). The position of the $i$ matters.
• Mistaking a divergent sum for a constant. The harmonic sum diverges: $\sum_{i=1}^{\infty} 1/i = \infty$. It is $\Theta(\log n)$ as a partial sum, but it is not bounded. Contrast with $\sum 1/i^2 = \pi^2/6$, which is bounded.
• Treating $(1/2)^n$ as "goes to zero so I can drop it" when working out exact closed forms. It does asymptotically, but for finite $n$ a sum like $2 - (1/2)^{n-1}$ is not exactly 2.
• Double-counting when splitting an index. If you split $\sum_{i=1}^{n}$ as $\sum_{i=1}^{m} + \sum_{i=m+1}^{n}$, the ranges must be disjoint. $\sum_{i=1}^{m} + \sum_{i=m}^{n}$ would include $a_m$ twice.

We now have the algebraic vocabulary — sigma notation, arithmetic and geometric and harmonic identities, telescoping, integral bounds — needed to convert almost any loop or recurrence into a clean asymptotic statement. In the next section we extend the same toolkit to recurrences directly, deriving the Master Theorem, which compresses the three-way comparison "leaves vs. internal vs. work per level" into a single recipe. Every recurrence we solve there will dissolve into one of the summations we just learned to evaluate.