The number of digits in n! (Part 4)

When I was in school, I stared at this graph for weeks, if not months, trying to figure out an equation for the number of digits in n!. And I never could figure it out. However, even though I was not able to figure this out for myself, there is a very good approximation using Stirling’s approximation. The next integer after \log_{10} n! gives the number of digits in n!, and

\log_{10} n! \approx \displaystyle \frac{\left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \displaystyle \frac{1}{2} \ln (2\pi)}{\ln 10}

The graph below shows just how accurate this approximation really is. The solid curve is the approximation; the dots are the values of \log_{10} n!. Not bad at all… the error in the curve is smaller than the size of the dots.

stirling

The following output from a calculator shows just how close the approximation to log_{10} 69! is to the real answer. There are also additional terms to Stirling’s series that would get even closer answers.

stirling69-2

stirling69

As I mentioned earlier in this series, I’m still mildly annoyed with my adolescent self that I wasn’t able to figure this out for myself… especially given the months that I spent staring at this problem trying to figure out the answer.

First, I’m annoyed that I didn’t think to investigate \log_{10} n!. I had ample experience using log tables (after all, this was the 1980s, before scientific calculators were in the mainstream) and I should have known this.

Second, I’m annoyed that I didn’t have at the tips of my fingers the change of base formula

\log_{10} n! = \displaystyle \frac{\ln n!}{\ln 10}

Third, I’m annoyed that, even though I knew calculus pretty well, I wasn’t able to get at least the first couple of terms of Stirling’s series on my own even though the derivation was entirely in my grasp. To begin,

\ln n! = \ln (1 \cdot 2 \cdot 3 \dots \cdot n) = \ln 1 + \ln 2 + \ln 3 + \dots + \ln n

For example, if n = 10, then \ln 10! would be the areas of the 9 rectangles shown below (since $\ln 1 = 0$):

stirlingintegralThe areas of these nine rectangles is closely approximated by the area under the curve y = \ln x between x =1\frac{1}{2} and x = 10\frac{1}{2}. (Indeed, I chose a Riemann sum with midpoints so that the approximation between the Riemann sum and the integral would be very close.)

In general, for n! instead of 10!, we have

\ln n! \approx \displaystyle \int_{3/2}^{n+1/2} \ln x \, dx

This is a standard integral that can be obtained via integration by parts:

\ln n! \approx \bigg[ \displaystyle x \ln x - x \bigg]_{3/2}^{n+1/2}

\ln n! \approx \left[ \left(n + \displaystyle \frac{1}{2} \right) \ln \left(n + \displaystyle \frac{1}{2} \right) - \left(n + \displaystyle \frac{1}{2} \right) \right] - \left[ \displaystyle \frac{3}{2} \ln \frac{3}{2} - \frac{3}{2} \right]

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln \left(n + \displaystyle \frac{1}{2} \right) - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1

We can see that this is already taking the form of Stirling’s approximation, given above. Indeed, this is surprisingly close. Let’s use the Taylor approximation \ln(1+x) \approx x for x \approx 0:

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln \left(n \left[1 + \displaystyle \frac{1}{2n}\right] \right) - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \left[\ln n + \ln \left(1 + \displaystyle \frac{1}{2n} \right) \right] - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \left[\ln n + \displaystyle \frac{1}{2n} \right] - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n + \left(n + \displaystyle \frac{1}{2} \right) \displaystyle \frac{1}{2n} - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n +\displaystyle \frac{1}{2} + \frac{1}{4n} - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \left(\displaystyle \frac{3}{2} - \displaystyle \frac{3}{2} \ln \frac{3}{2} \right) + \displaystyle \frac{1}{4n}

By way of comparison, the first few terms of the Stirling series for \ln n! are

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \displaystyle \frac{1}{2} \ln (2\pi) + \displaystyle \frac{1}{12n}

We see that the above argument, starting with an elementary Riemann sum, provides the first two significant terms in this series. Also, while the third term is incorrect, it’s closer to the correct third term that we have any right to expect:

\displaystyle \frac{3}{2} - \displaystyle \frac{3}{2} \ln \frac{3}{2} \approx 0.8918\dots

\displaystyle \frac{1}{2} \ln (2\pi) \approx 0.9189\dots

The correct third term of \displaystyle \frac{1}{2} \ln(2\pi) can also be found using elementary calculus, though the argument is much more sophisticated that the one above. See the MathWorld website for details.

Leave a comment

1 Comment

  1. The number of digits of n!: Index | Mean Green Math

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: