4.5: Summing series

For the final example of what pictures can explain, return to the factorial function. Our first approximation to n! began with its integral representation and then used lumping (Section 3.2.3).

Lumping, by replacing a curve with a rectangle whose area is easily computed, is already a pictorial analysis. A second picture for n! begins with the summation representation

\[ln n! = \sum{1}^{n} lnK. \label{4.45} \]

This sum equals the combined area of the circumscribing rectangles.

Problem 4.30 Drawing the smooth curve

Setting the height of the rectangles requires drawing the \(lnk\) curve which could intersect the top edge of each rectangle anywhere along the edge. In the preceding figure and the analysis of this section, the curve intersects at the right endpoint of the edge. After reading the section, redo the analysis for two other cases:

a. The curve intersects at the left endpoint of the edge.

b. The curve intersects at the midpoint of the edge.

That combined area is approximately the area under the \(lnk\) curve, so

\[ln n! ≈ \int_{1}^{n} ln k dk = n lnn - n + 1. \label{4.46} \]

Each term in this \(lnn\)! approximation contributes one factor to n!:

\[n! ≈ n^{n} x e^{-n} x e. \label{4.47} \]

Each factor has a counterpart in a factor from Stirling’s approximation (Section 3.2.3). In descending order of importance, the factors in Stirling’s approximation are

\[n! ≈ n^{n} x e^{-n} x \sqrt{n} x \sqrt{2\pi}. \label{4.48} \]

The integral approximation reproduces the two most important factors and almost reproduces the fourth factor: e and \(\sqrt{2π}\) differ by only 8%. The only unexplained factor is \(\sqrt{n}\).

Question

From where does the \(\sqrt{n}\) factor come?

The \(\sqrt{n}\) factor must come from the fragments above the \(lnk\) curve. They are almost triangles and would be easier to add if they were triangles. Therefore, redraw the \(lnk\) curve using straight- line segments (another use of lumping).

The resulting triangles would be easier to add if they were rectangles. Therefore, let’s double each triangle to make it a rectangle.

Question

What is the sum of these rectangular pieces?

To sum these pieces, lay your right hand along the \(k = n\) vertical line. With your left hand, shove the pieces to the right until they hit your right hand. The pieces then stack to form the \(lnn\) rectangle. Because each piece is double the corresponding triangular protrusion, the triangular protrusions sum to \((lnn)/2\). This triangle correction improves the integral approximation. The resulting approximation for ln n! now has one more term:

\[lnn n! ≈ \underbrace{nlnn - n + 1}_{\text{integral}} + \underbrace{\frac{lnn}{2}}_{\text{triangles}} \label{4.49} \]

Upon exponentiating to get n!, the correction contributes a factor of \(\sqrt{n}\).

\[n! ≈ n^{n} x e^{-n} x e x \sqrt{n}. \label{4.50} \]

Compared to Stirling’s approximation, the only remaining difference is the factor of e that should be \(2\pi\), an error of only 8% all from doing one integral and drawing a few pictures.

Multiple problems

Problem 4.31 Underestimate or overestimate?

Does the integral approximation with the triangle correction underestimate or overestimate n!? Use pictorial reasoning; then check the conclusion numerically.

Problem 4.32 Next correction

The triangle correction is the first of an infinite series of corrections. The corrections include terms proportional to \(n − 2, n − 3\), ..., and they are difficult to derive using only pictures. But the \(n − 1\) correction can be derived with pictures.

a. Draw the regions showing the error made by replacing the smooth ln k curve with a piecewise-linear curve (a curve made of straight segments).

b. Each region is bounded above by a curve that is almost a parabola, whose area is given by Archimedes’ formula (Problem 4.34)

\[\text{area} = \frac{2}{3} x \text{area of the circumscribing rectangle}. \label{4.51} \]

Use the propoerty to approxiamte the area of each region.

c. Show that when evaluating \(ln n! = \sum_{1}^{n}\) \(ln k\), these regions sum to approximately \((1 − n^{−1})/12\).

d. What is the resulting, improved constant term (formerly e) in the approximation to n! and how close is it to \(2\pi\)? What factor does the \(n − 1\) term in the \(ln n!\) approximation contribute to the n! approximation?

These and subsequent corrections are derived in Section 6.3.2 using the technique of analogy.