Background required : calculus, specifically integration

By representing a sum as an area, it is often possible to estimate its size by approximating it with the area underneath a curve.

For example, suppose we wish to compute the sum . There’s no known closed formula for b_n but we can get a pretty good grasp of its size in terms of n. Consider the graph of y = 1/x:

(Diagram edited from a graph plotted by wolframalpha.)

In both instances, the sum 1 + 1/2 + … + 1/n represents the area of the red region. From the diagram, it’s clear that this sum is at most and at least . Thus:

In particular and it represents the area of the “white space” from x=1 to x=n on the left graph above. Since is an increasing sequence which is bounded from above, it must converge to some value. This is known as Euler’s gamma constant and an entire book has been written on it.

Anyway, we now know the following.

The sequence 1 + 1/2 + 1/3 + … + 1/n diverges to infinity and 1 + 1/2 + 1/3 … + 1/n – log(n) converges to a real number < 1.

By the same token, if s > 1 is a real number, we have:

The LHS is and the RHS is . In particular, since the sum is bounded above by 1 + 1/(s-1) it must converge!

If s>1 is a real number, then converges as .

Stirling’s Approximation

Using this technique, we can also approximate n!, or rather, log(n!) = log(1) + log(2) + … + log(n). We shall approximate this sum with the area under the curve y = log(x) from x=1 to x=n. Via integration by parts, we have:

So the sum log(1) + … + log(n) is about n(log n – 1) and

A more precise analysis would give us , but we won’t go into that detail.

In summary, sums are generally much more difficult to compute than integrals (by that, we mean partial sums of the form ). For example, consider the infinite sum where k>1 is a fixed integer. For even k, there is a nice closed form for it: specifically it is a rational multiple of . The details of that would be another story for another day. For now, it suffices to say that integrals are a useful means to approximate sums.