Discrete Math and Proof

Summations, series, and asymptotic sums

Adding many terms and estimating the total

~11 minLesson 12 of 19Written by Claude Opus 4.8

Every time you ask "how many steps does this loop take?", you are secretly adding up a series. A loop that does $i$ units of work on its $i$ -th pass costs $1 + 2 + 3 + \dots + n$ - and knowing that this equals $\frac{n ( n + 1 )}{2}$ is the difference between guessing "it's a loop, so roughly $n$ " and knowing "it's $O (n^{2})$ ." Summations are the arithmetic layer directly under Big-O.

The picture to hold in your head

A summation is a for-loop written in one line. The Greek

Σ

is the loop; the little numbers say where the counter starts and stops; the expression to its right is the body that gets added each pass. The whole prize of this lesson is the closed form - a formula with no loop left in it, so you can read off the answer (and its Big-O) in a single glance instead of running the loop in your head.

Sigma: a loop you can solve on paper

The notation $\sum_{i = 1}^{n} a_{i}$ means "let $i$ walk from $1$ to $n$ , and add up $a_{i}$ each time." So $\sum_{i = 1}^{4} i = 1 + 2 + 3 + 4 = 10$ . That is just running the loop. The magic is that many loops collapse into a formula. The most famous - the one legend says a young Gauss found in seconds - pairs the first term with the last, the second with the second-last, and so on:

1 + 2 + \dots + n = i = 1 \sum n i = \frac{n ( n + 1 )}{2} .

Each of the $n$ terms pairs up to make $n + 1$ , and there are $n /2$ such pairs - hence $\frac{n ( n + 1 )}{2}$ . The leading term is $\frac{n ^{2}}{2}$ , so a nested loop that runs this many times is $O (n^{2})$ . That single fact is why summations and Big-O are the same subject seen from two angles.

The four closed forms worth memorising

Arithmetic (a fixed step $d$ each term) - sum grows quadratically:

i = 1 \sum n i = \frac{n ( n + 1 )}{2}, i = 1 \sum n i^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6} .

Geometric (a fixed ratio $r$ each term) - the workhorse of divide-and-conquer:

i = 0 \sum n - 1 r^{i} = \frac{1 - r ^{n}}{1 - r} (r \neq = 1), i = 0 \sum \infty r^{i} = \frac{1}{1 - r} if ∣ r ∣ < 1.

Harmonic - the slow one; it diverges, but only as fast as a logarithm:

H_{n} = i = 1 \sum n \frac{1}{i} \approx ln n + γ, γ \approx 0.5772.

Watch the sum build itself

Time to see these grow. Below, each term is drawn as a bar; every new amber slice is the term $a_{i}$ just added, and the whole column's height is the running total $S_{i}$ . The blue line is the closed form - and the key "aha" is that every column top lands exactly on it. Pick a family, drag the number of terms, and in geometric mode drag the ratio $r$ : below $1$ the bars shrink and the total glides up to a ceiling; at or above $1$ they never stop growing.

Sigma-notation playground∑ i · arithmetic

the term aᵢ just addedsum of earlier termsclosed-form curve Sₙ

familyterms n = 8

ratio r = 0.5

terms n8

running total Sₙ36

n(n+1)/236

∑ i from 1 to 8 = 36 = n(n+1)/2 - a nested loop over this is O(n²).

The aha: shrinking terms can still add to a finite total

Switch to geometric and set

r = 0.5

. The bars halve each step -

1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \dots

- and the running total climbs toward, but never passes, the dashed ceiling at

\frac{1}{1 - r} = 2

. That is convergence: infinitely many terms, one finite sum. Now drag

r

up past

1

. Each term is now bigger than the last, the ceiling vanishes, and the total diverges to infinity. The whole fate of the series hinges on one number: whether

r

is below

1

Telescoping, harmonic, and the integral squeeze

Not every sum needs a memorised formula. A telescoping sum is one where each term splits into two pieces that cancel their neighbours, so the whole thing collapses to just the ends. Watch the middle evaporate:

i = 1 \sum n \frac{1}{i ( i + 1 )} = i = 1 \sum n (\frac{1}{i} - \frac{1}{i + 1}) = 1 - \frac{1}{n + 1} .

The $- \frac{1}{2}$ from the first term cancels the $+ \frac{1}{2}$ of the second, and so on down the line - only the very first and very last survive. This trick underlies more running-time proofs than you'd expect.

The harmonic series $H_{n} = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ has no tidy closed form, so we bound it instead. Because $\frac{1}{x}$ is a smooth decreasing curve, the sum of the rectangles under it is trapped between two integrals - this is the light-touch idea of bounding a sum with an integral:

ln (n + 1) \leq i = 1 \sum n \frac{1}{i} \leq 1 + ln n .

Both walls are $ln n$ plus a constant, so $H_{n} = Θ (lo g n)$ . In the demo, harmonic mode draws exactly this: the staircase of bars hugs the smooth $ln n + γ$ curve. The series does diverge - add enough terms and it exceeds any number - but so slowly that reaching a sum of just $20$ takes over $270$ million terms. That gentle logarithmic creep is precisely the cost of the balanced-tree and heap operations you have already met.

from math import log

n = 8
# arithmetic: 1 + 2 + ... + n
print(sum(range(1, n + 1)))          # 36  (the loop)
print(n * (n + 1) // 2)             # 36  (O(1) formula)

# geometric: 1 + r + r^2 + ... (n terms)
r = 0.5
print(sum(r**i for i in range(n)))    # 1.9921875
print((1 - r**n) / (1 - r))         # 1.9921875  (same)

# harmonic grows like ln n
print(sum(1/i for i in range(1, n+1)))  # 2.7179
print(log(n) + 0.5772)              # 2.6566  (H_n ≈ ln n + γ)

Closed forms beat loops - same answer, no iteration

Check yourself

A loop nested inside a loop, where the inner one runs i times on the i-th outer pass, does total work:

For a positive ratio r, the infinite geometric sum ∑ rⁱ (i from 0 to ∞) reaches a finite total only when:

Recall: the closed form for ∑ i from 1 to n, and why it forces a nested loop to be O(n²).

Try to state it, then check.

Primary source

MIT's 6.042J - Mathematics for Computer Science devotes full units to sums and series: Gauss's pairing trick, geometric and harmonic sums, telescoping, and bounding sums with integrals, all built for CS. For where these sums come from - the running-time recurrences of real algorithms - see 6.006 - Introduction to Algorithms.

Ask your teacher

Here is the connection worth carrying forward: summations are Big-O analysis (Lesson 5). Counting the work of a loop always means summing a series - and a nested loop is nothing more than

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

. Master the closed forms and Big-O stops being memorised trivia and becomes something you can derive. Ask me how the geometric series explains why merge sort's

\sum 2^{k} \cdot \frac{n}{2 ^{k}}

collapses to

O (n lo g n)

, or how the harmonic series pins down the cost of building a balanced tree.