Common summations in computer science

Gauss’s sum: 1 + 2 + 3 + … + n

The sum

1 + 2 + 3 + … + n

Simplifies to

n(n+1) / 2.

Notice that this quantity is Θ(n²).

This shortcut arises frequently in the analysis of algorithms like insertion sort or selection sort.

Numbers of the form n(n+1)/2 are called the triangular numbers.

Sums of Powers of Two: 1 + 2 + 4 + 8 + 16 + …

The sum

2⁰ + 2¹ + 2² + … + 2^n-1

simplifies to 2ⁿ - 1. This explains why the maximum value that can be stored in an unsigned 32-bit integer is 2³² - 1.

Sum of a geometric series: r^0 + r^1 + r^2 + …

The sum of the geometric series

r⁰ + r¹ + r² + … + r^n-1

In the case where r ≠ 1, simplifies to (rⁿ - 1) / (r - 1). If r < 1, this sum is bounded from above by 1 / (1 - r).

If r = 1, this sum is rn.

Fencepost Sums

Here we consider sums of the form

a + b + a + b + … a

vs.

a + b + a + b + … b

To visualize these sums, imagine a section of fence alternating between posts and rails. Three scenarios are possible.

Imagine a section of fence with posts at each end, connected by rails. n rails require n+1 posts. Conversely p posts are joined by p-1 rails.

|—|—|—|

Imagine a section of fence with a post at one end, but but an open rail at the other. n rails require n posts.

|—|—|—

or

—|—|—|

Imagine a section of fence with open rails at both ends. n rails require n-1 posts. Conversely, p posts are joined by p+1 rails.

—|—|—

Calculations like this arise in situations such as the layout of graphical objects where the sizes of the objects must be summed and the spaces between the objects must also be summed. In such situations it is important to be aware of whether or not the intent is to have spaces at each end.

The total width of such a fence will always be:

(width of post) x (number of posts) + (width of rail) x (number of rails)

But caution must be used in computing the number of posts and number of rails so as to avoid a so-called off-by-one error. Mistakes of this kind are common.

Sums of Fibonacci Numbers

The Fibonacci numbers are defined inductively as

F₀ = 0
F₁ = 1
F_n+2 = F_n + F_n+1

The sum of the first n+1 Fibonacci numbers is given by

F₀ + F₁ + F₂ + … + F_n = F_n+2 - 1.

This summation arises, among other places, in the analysis of Fibonacci heaps, where it’s used to provide a lower bound on the number of nodes in each tree in the heap.

Sums of reciprocals: 1/1 + 1/2 + 1/3 + 1/4 + …

The summation

1/1 + 1/2 + 1/3 + 1/4 + … + 1/n

is equal to the nth harmonic number, denoted H_n. The nth harmonic number obeys the inequalities

ln (n + 1) ≤ H_n ≤ (ln n) + 1

and therefore H_n = Θ(log n). The harmonic numbers often arise in the analysis of algorithms, with randomized quicksort being a particularly nice example.

Sums of reciprocal squares: 1/1 + 1/4 + 1/9 + 1/16 + 1/25 + …

The summation

1/1 + 1/4 + 1/9 + 1/16 + …

out to infinity converges to π² / 6, and therefore any summation of the form

1/1 + 1/4 + 1/9 + 1/16 + … + 1/n²

is Θ(1).