Geometric series

A geometric series is the sum of the terms of a geometric progression: a list $a, ar, ar^2, \dots$ in which each term is the previous term times a fixed ratio $r$. For $r \ne 1$ the sum of the first $n+1$ terms of $1, r, r^2, \dots$ is $(r^{n+1} - 1)/(r - 1)$. When $r$ is a positive constant other than 1, the sum is $\Theta$ of its largest term, in asymptotic notation. This rule gives many bounds in the analysis of algorithms in one line.

In plain words

Take a stick of length 1. Cut off half of it, then half of what is left, then half again. The pieces have lengths 1/2, 1/4, 1/8, and so on. All the pieces together never pass the original length 1. A sum in which each term is a fixed fraction of the previous term is small: it is at most a constant times the first term.

Now reverse the direction. Each term is twice the previous one. The last term is then larger than all the earlier terms together. So the sum is less than twice the last term. In both cases one end of the sum decides the size of the whole sum, and the other terms add only a constant factor.

The idea

Finite sum. For each real $r \ne 1$ and each integer $n \ge 0$,

For $r = 1$ the sum is $n + 1$. With a first term $a$, each term is multiplied by $a$, so $\sum_{k=0}^{n} a r^k = a\,(r^{n+1} - 1)/(r - 1)$ for $r \ne 1$. The factor $a$ does not change the rule below.

Proof. Let $S = \sum_{k=0}^{n} r^k$. Then $rS = \sum_{k=1}^{n+1} r^k$. The two sums share the terms $r^1, \dots, r^n$. So $rS - S = r^{n+1} - r^0$, that is $(r - 1)S = r^{n+1} - 1$. Divide by $r - 1$, which is not zero. $\square$

Infinite sum. For real $r$ with $|r| < 1$, $r^{n+1} \to 0$ when $n \to \infty$. So the partial sums converge and

For real $r$ with $|r| \ge 1$ the terms do not tend to 0 and the series diverges. A common case is $\sum_{k \ge 0} 2^{-k} = 2$, with ratio $1/2$.

The largest term rule. Let $r$ be a constant with $r > 0$ and $r \ne 1$, and let $S_n = \sum_{k=0}^{n} r^k$.

• If $r > 1$, then $r^n \le S_n < \frac{r}{r-1}\, r^n$. So $S_n = \Theta(r^n)$, the last term.
• If $r < 1$, then $1 \le S_n < \frac{1}{1-r}$. So $S_n = \Theta(1)$, the first term.

Proof. Each term is positive, so $S_n$ is at least its largest term. This is $r^n$ if $r > 1$ and $r^0 = 1$ if $r < 1$. For $r > 1$, the closed form gives $S_n = (r^{n+1} - 1)/(r-1) < r^{n+1}/(r-1)$. For $r < 1$, the infinite sum bounds the partial sum: $S_n < 1/(1-r)$. $\square$

The constants depend on $r$. They grow when $r$ comes close to 1: for $r = 2$ the factor is 2, for $r = 1.01$ it is about 101.

Bounding by a geometric series. A series that is not exactly geometric can still be bounded by one. If $a_k \ge 0$ and $a_{k+1} \le r\,a_k$ for each $k$, with a constant $0 < r < 1$, then $a_k \le a_0 r^k$ by induction, so $\sum_{k \ge 0} a_k \le a_0/(1-r)$. For example, in $\sum_{k \ge 1} k/3^k$ the ratio of consecutive terms is $(k+1)/(3k) \le 2/3$, so the sum is at most $(1/3)/(1 - 2/3) = 1$. The exact value is $3/4$.

The weighted sum $\sum k/2^k$. For $\sum_{k \ge 1} k\, 2^{-k}$ there is a short proof with no calculus. Write $k = \sum_{j=1}^{k} 1$. Then $\sum_{k \ge 1} k\,2^{-k} = \sum_{j \ge 1} \sum_{k \ge j} 2^{-k}$, where the order of summation can change because all terms are non-negative. The inner sum is $2^{1-j}$ by the infinite geometric sum. So the total is $\sum_{j \ge 1} 2^{1-j} = 2$. The same exchange of sums gives the general form: for $|x| < 1$, the inner sum is $\sum_{k \ge j} x^k = x^j/(1-x)$, so $\sum_{k \ge 0} k\,x^k = \sum_{j \ge 1} x^j/(1-x) = x/(1-x)^2$. The exchange is valid for negative $x$ too, because the series converges absolutely.

Examples

Exact values. For $r = 3$ and $n = 5$: $1 + 3 + 9 + 27 + 81 + 243 = 364 = (3^6 - 1)/2$. For $r = 2$ and $n = 4$: $1 + 2 + 4 + 8 + 16 = 31 = 2^5 - 1$.

Non-example. The rule needs a constant ratio. Take $r = 1 + 1/n$ with $n + 1$ terms. The last term is $(1 + 1/n)^n < e$, but the sum is $n\big((1 + 1/n)^{n+1} - 1\big)$, which is about $(e - 1)\,n$. So the sum is $\Theta(n)$ while the largest term is $\Theta(1)$. The sum of a series with $r = 1$ is also not covered: it is $n + 1$, and each term is the largest.

Where it is used

Array doubling. A dynamic array starts with capacity 1 and doubles its capacity when it is full. The copies happen at sizes $1, 2, 4, \dots, 2^m$, where $m$ is the integer with $2^m < n \le 2^{m+1}$ (for $n \ge 2$). The total number of copied items is $2^{m+1} - 1 < 2n$. For example, 17 appends copy $1 + 2 + 4 + 8 + 16 = 31$ items, and $31 < 34$. So the copies cost $O(1)$ per append on average over the sequence, which is an amortized bound.

Recursion trees. Sum the cost of a recursion tree level by level. Often the level costs form a geometric progression, and the rule gives the answer from one end.

• For $T(n) = 2T(n/2) + n^2$ the cost of level $i$ is $2^i (n/2^i)^2 = n^2/2^i$. The ratio is $1/2$, so the sum over $i = 0, \dots, \lg n$ is at most $2n^2$ and at least $n^2$. The root decides: $T(n) = \Theta(n^2)$.
• For $T(n) = 3T(n/2) + n$ the cost of level $i$, for $i = 0, \dots, \lg n$, is $n(3/2)^i$. The ratio is $3/2$, so the last level decides. It costs $n (3/2)^{\lg n} = n^{\lg 3}$, so $T(n) = \Theta(n^{\lg 3})$.
• When the ratio is exactly 1 each level costs the same, and the total is the number of levels times the cost of one level. This is the middle case of the master theorem.

Building a heap. The bottom-up construction of a binary heap calls a sift-down at each internal node. A node of height $h$ costs at most $h$ swaps. A heap of $n$ nodes has at most $\lceil n/2^{h+1} \rceil$ nodes of height $h$, and for $0 \le h \le \lfloor \lg n \rfloor$ this is at most $n/2^h$, because $n/2^{h+1} \ge 1/2$ and $\lceil x \rceil \le 2x$ for $x \ge 1/2$. So the total number of swaps is at most

The build takes $O(n)$ time, not the $O(n \log n)$ that the bound $h \le \lg n$ for each node suggests. The first phase of heapsort uses this.

References

1. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, fourth edition, Appendix A, Summations; Section 6.3 for the heap bound
2. Graham, Knuth and Patashnik, Concrete Mathematics, second edition, Chapter 2, Sums
3. Donald E. Knuth, The Art of Computer Programming, Volume 1, third edition, Section 1.2.3, Sums and products