Stirling's Formula

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

PROFESSOR: Our method for estimating sums can also be used to estimate products, basically by taking logs to turn a product into a sum. And we're going to use that to come up with another important estimate of a quantity that will come up, really, very regularly called n factorial.

S n factorial is the product of the first n integers, 1 times 2 up through n minus 1 times n. In concise product notation, it's the product-- that's pi, capital pi, for product-- from i equals 1 to n of i. And its standard abbreviation is to write it as n! pronounced n factorial.

So what I'd like to do is get an asymptotic estimate for n factorial. Again, n factorial is one of these quantities where there isn't any exact formula that doesn't have those ellipses in it. There's no short formula with basic operations fixed size of formula that expresses n factorial. But we get a nice formula for a tight asymptotic estimate.

So as I said, the first trick is to turn the product into a sum by taking logs. So log of n factorial is the log of 1-- the product of 1 through n. But a log of a product is the sum of the logs, so it's simply log of 1 plus log of 2 up through log of n. And expressed in sum notation, it's the sum from i equals 1 to n of log of i.

Now, the integral method gives us a way to estimate this sum by bracketing it between the values of some integrals, namely restating the integral method for sum-- for bounding integrals by sums. This time, we're looking at an increasing function because it's log of x.

Let f be a weakly increasing function from positive reals the positive reals. I'm interested in the sum from i equals 1 to n of f of i. And I want to relate it and bound it by the integral from 0-- from 1 to n of f of x where, in this case, the particular f that we're interested in is f of x is log x.

And the theorem says that with increasing functions s is bracketed between the integral plus the last term in the sum and the integral plus the first term in the sum. Remember, since the function is weakly increasing, f of 1 is smaller than f of n. So that's the way you remember which way the bounds go.

So s is between I plus f of 1 and I plus f of n by our general formula for applying integral bounds to sums. Well, what that tells us then is that the sum from 1 to n of log of i, which is what we're interested in, is bracketed between the integral from 1 to n of log x and the integral from 1-- well, it's plus log of 0, but-- log of 1 rather, but that's 0. And the integral from 1 to n of log of x plus the last term, which is log of n.

In case you don't remember from first term calculus, the integral of log of x is, in fact-- has the indefinite integral is x log of x over e, which you can easily check by differentiating x log x over e. ln means natural log, remember. In computer science, L-O-G, log means log to the base 2 unless you explicitly put some base on it like log, L-O-G, sub 10.

So ln is the natural log from calculus. And plugging in this value for the indefinite integral of log of x and using the bounds 1, n, what we come up with is that the sum of the logs is bounded between n times log n over e and n times log n over e plus log of n.

It's a pretty tight bounds. What that means is that informally speaking, the sum of the logs is about this term plus that term. Plus, let's take the average value of that term, which is half this term. So we could say that the sum of logs is approximately equal. That's a little vague, but live with it. n log n over e plus half of log n.

Well, now, if I'm interested, remember, in an estimate for n factorial-- so let's exponentiate both sides. So taking e to this sum gives me a product of e to this times e to that. Well, e to this is-- really, it's e to the log of n over e to the nth power, which means it's n over e to the n. And this is e to the log of n to the power half, or square root of n. So we wind up with n factorial is approximately equal to the square root of n times n over e to the n.

Now, this approximately equal is imprecise. It's not asymptotically equal because we were doing an arithmetic average of 0 and log n over 2. In addition, it's very dangerous when you have two things that are approximately equal to exponentiate them and expect that they're still approximately equal. Often, they aren't.

But nevertheless, this is a kind of a heuristic derivation of some kind of asymptotic estimate that we would expect that n factorial was roughly like the square root of n times n over e to the nth power. And it turns out that it's-- that this heuristic gives a pretty accurate answer.

A precise approximation is that n factorial is actually asymptotically equal to the square root of 2 pi n times n over e to the n. And we're not going to prove that. It requires elementary calculus, but more than we want to take time for.

And this crucial formula that we will be using very regularly to estimate the size of n factorial is called Stirling's Formula, and it's one to have on your crib sheets if you haven't memorized it.

Free Downloads

Video


Caption

  • English-US (SRT)