Estimating Sums Via Integration

Background required : calculus, specifically integration

By representing a sum \sum_{i=1}^n a_i 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 b_n = 1 + \frac 1 2 + \frac 1 3 + \dots + \frac 1 n. There’s no known closed formula for bn 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 1 + \int_1^n \frac 1 x dx = 1 + \log n and at least \int_1^{n+1} \frac 1 x dx = \log(n+1). Thus:

\log(n+1) \le b_n = 1 + \frac 1 2 + \dots + \frac 1 n \le 1 + \log n.

In particular b_n - \log n \le 1 and it represents the area of the “white space” from x=1 to x=n on the left graph above. Since b_n - \log n 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:

\int_1^{n+1} x^{-s} dx \le 1 + \frac 1 {2^s} + \frac 1 {3^s} + \dots + \frac 1 {n^s} \le 1 + \int_1^n x^{-s} dx.

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

If s>1 is a real number, then 1 + 1/2^s + 1/3^s + \dots + 1/n^s converges as n\to \infty.

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:

\int \log x \cdot dx = x(\log x - 1) + c.

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

n! \approx e^{n(\log n -1)} = \left( \frac n e\right)^n.

A more precise analysis would give us n! \approx \sqrt{2\pi n} (\frac n e)^n, 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 b_n = a_1 + a_2 + \dots + a_n). For example, consider the infinite sum 1 + 1/2^k + 1/3^k + \dots 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 \pi^k. 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.

This entry was posted in Notes and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s