The most beautiful formula in mathematics is certainly not the triviality , as claimed by many tasteless mathematicians with no self-esteem, but rather Stirling's formula, stating that . Quantifying the error of this approximation can be done to any precision using the Euler-MacLaurin complicated formula, but it is often handy to have a simpler estimation; Herbert Robbins found one (original note here) which is surprisingly accurate:
The inequalities are strict and valid for every . The proof of this result is given below. For future reference, we can compare (1) with the higher-order expansion:
We have . Robbins' proof consists in a subtle approximation of , as seen as the area of the rectangle . This area is equal to:
the area of the points in the rectangle under the curve , that is , (in the picture, it's the pink+black zone)
plus the area of the triangle between the points , (blue+black zone)
minus the area of the small black zone we counted twice, which is equal to minus the area of the points in the rectangle that are not in the preceding triangle.
Clearly, . We also recall that the antiderative of is . Consequently, noting ,
How big is ? Well, first we can reckon the : they are equal to minus the area of the trapezoidal approximation of , which is :
Now you might want to develop the determinant as : don't do this. Instead, do the following dark magic: first, note that where . Then, use the analytic formula
We now use this to bound below and above.
Since are all greater than 3,
On the other hand, are smaller than , so
It turns out that (develop both sides then dismiss some terms), so that
From the preceding bounds we see that the series is indeed convergent. If is its sum, and using again the precedings bounds (they are telescoping), we can estimate:
Now go back last line of (1). Take exponentials to get . Then, with and the estimate above,
It's obviously not over, since we didn't get the constant . This, however, is usually done by another means, typically with the Wallis integral asymptotics as they here.
|| Herbert Robbins does not have the fame he deserves. He's the Robbins of the Robbins-Munro algorithm, the Lai-Robbins bound on bandit algorithms, the backward algorithm for the secretary problem: three essential contributions to different domains of statistics and computational mathematics. His book What is Mathematics ? with Courant is a masterpiece.