Two nice approximations for n!

[@emanuellandeholm5657]

The first ineq is actually quite tight. sqrt (2 pi) is ~ 2.5 and Euler's constant is 2.718...

[@RobertBraf]

But how did mathematicians like Mr. Stirling sit down at candle light and think "Hey, I might approximate n! using an inequality based on the integral of ln(x) between n and n+1, so let's do it... “. How can such a thought ignite? 😮 I like mathematics since school days but thinking about this fascinates me every time again and again...

[@crimsonvale7337]

I would assume stirling’s approximation comes from trying to do numeric approximations for integrals, the motivation of a trapezoid approximating an area is a common concept ig.

[@xinpingdonohoe3978]

Maybe it's because sums of logs are logs of products, so to get the product he wants, he exploited logs and sums.

[@roberttelarket4934]

Stirling was not one of the ancient mathematicians which refers to the Greeks and others from that very past era. He was from about 3 centuries ago.

[@RobertBraf]

@@roberttelarket4934 of course. 👍 Maybe ancient is a too strong adjective here so I removed it... 😁

[@bilkishchowdhury8318]

It is very well known that sum of a function evaluated at integers can be approximated by the integral of that function. The integral test for convergence of infinite sums, harmonic series's relation to logarithms, Euler-Maclaurin formula all use this concept.

[@StanleyDevastating]

Typo at @15:04. We should have 2^(2n+1/2), not 2^(2n+1). This does not affect the next line which is correct.

[@ej2953]

My favorite use of factorals is to show that given any n, you can find a contiguous* sequence of n integers that does not contain a prime. That is one nice result that many people without much of a math background can understand. * Somehow overlooked the inclusion of "contiguous" in the sentence.

[@vibhupandya6103]

Can't you just have 4,6,8,...,(2n+2)? What's the factorial got to do with it

[@ej2953]

@@vibhupandya6103 Oops. I meant to say "contiguous sequence". Sorry about that. I'll edit the previous post.

[@Buridan84]

13:04 - ominous fraction bar appears out of nowhere 😄

[@Zersetzor]

24:08 A good place to what?! You can't just stop the video with such a cliffhanger!

[@Calcprof]

Ah. This is one way (more or less elementary) to get the constant (sqrt(2 pi)) in Sterling.

[@Balequalm]

Right? It was really well done, and used very little.

[@beniborukhov9436]

At around 22:15 don't we end up with 2 < 2 as a strict inequality?

[@miloszforman6270]

This inequality on top of the board: (1+1/n)^n of course only holds if n>1. For n=1 it becomes an equality. That's not too important for the following.

[@pranavsingla5902]

at 16:29 there should be a root(2) in the numerator after simplifying, right? I'm getting it to be [sqrt(2) * (a_n)^2 * sqrt(n)] / [a_2n * sqrt(2n+1)]

[@miloszforman6270]

Not quite. In the line above, it should read "2^(2n+1/2)", coming from the Wallis product at 14:55, rather than "2^(2n+1)". This last expression is faulty, missing the tiny denominator "2" of "1/2".

[@cernejr]

How about also discussing the result a little? How tight are the inequalities? Where would a physicist or an applied mathematician use them?

[@Sam27182]

I got taught Stirling's Approximation in physics classes, specifically statistical mechanics/thermodynamics, to calculate large factorials quickly. Also the logarithm version that ignores the constant (nln(n)-n). You frequently need to know the number of ways to arrange particles, so its a way to calculate numbers that would otherwise be uncalculatable.

[@forcelifeforce]

@@Sam27182 "the constant (nln(n)-n)." As long as n is a variable, that is not a "constant."

[@Sam27182]

@@forcelifeforce See my reply to the other comment. The constant term is sqrt(2pi), which is ignored. The sqrt(n) also turns out to be pretty inconsequential. What is left after this is (n/e)^n, and taking the log leaves nln(n)-n

[@thelocalsage]

Only time I’ve seen any of these was Stirling’s approximation, which has clear utility in stat mech as has been already pointed out. not sure when the others get used, but i doubt it’s never. You can very easily determine how tight the first one is seeing as they are only off by a scalar… sqrt(2pi) vs. e shouldn’t be too tough for your calculator to handle.

[@ΒασίλειοςΚαρατσούλας]

These proofs are definitely in The Book ( This is an excellent Erdös reference btw)

[@DeanCalhoun]

fun little video. some classic tricks from college real analysis class popping up all over the place

[@QuantumHistorian]

Looking at the last inequaliy, I was curious as to how good [(n+1)/e]^n would be as an approximation. The answer is damn good! To give an example, using n=1000, this is a lower bound off by a factor of ~30, while [(n+1)/3]^n is off by 10^44 and [(n+1)/2]^n over by a factor of 10^132. In fact, [(n+1)/e]^n is even better than the "lazy" Stirling approximation of n!=e^(n ln(n) - n), meaning it's off by less than a factor of sqrt(n). Not bad for such a simple expression! Might become by go to back-of-the-envelope approximation for n!

[@miloszforman6270]

Replacing n by n+1 gives you an extra factor (1+1/n)^n of approximately e: (n+1)^n = (n(n+1)/n)^n = n^n (1+1/n)^n and it is well known that lim [n-->oo] (1+1/n)^n = e. However, this factor e is already included if we replace the step function f(x) = ∑ [n

[@xizar0rg]

How is "2 < 2^1 / 1^0 < 3" legit? (last line, middle column, last board)

[@Catilu]

In fact, the second set of inequalities is not actually strict. If you put n=0, you get equality, so the point is, it should be weak, not strict

[@vanditseksaria5897]

@@Catilu the main purpose of the inequality is to study or approximate n! for large values of n

[@AbstractNoesis]

17:42

[@xizar0rg]

@@Catilu When writing out the binomial approximation for e (around 18min) he explicitly states that n is greater than 1. Is he misspeaking at this point?

[@arbel8160]

I think you should just assume n>1

[@jerrysstories711]

The first one is pretty useful, I've used it. The second one is so crazy wide, I don't know when you'd actually be able to use it.

[@OliverJennrich]

If you allow n=1, the second inequality must have an "

[@vibhupandya6103]

The first one with the lower bound is used all the time in stat mech. We usually skip the factor of sqrt(2pi n) cuz we work with logs, and log(n) is pretty small as compared to nlogn and n when n is as large as avogadro's number

[@franksaved3893]

If the an sequence is decreasing and bounded from below by 0, why L cannot be 0? If L is 0 this ruins the calculation at 16:16

[@hakerfamily]

I saw that too. I’m sure it can be patched up, but it’s a problem.

[@chemicalbrother5743]

Because no a_n is equal to 0

[@prag9582]

@@chemicalbrother5743your argument doesnt hold. Take for exemple the sequence 2^(1-n), whose limit is zero, and the term is never zero

[@JTISD3LL]

This is indeed an issue. Here's one solution (although there's almost certainly a simpler one). I will show that the terms of the a_n sequence are in fact bounded below by 1. Let J(n) be the area under the graph of ln on the interval [1,n]. I.e., J(n) is the integral over t ∈ [0,n] of ln(t). Since ln is concave, we can bound J(n) below by the sum of areas A(k) of trapezoids with base [k,k+1] and top corners at height ln(k) and ln(k+1) (these are just the same trapezoids as Michael uses at the start of the video). Write S(n) = A(1) + A(2) + ... + A(n-1) for this sum of areas of trapezoids. Again, S(n) ≤ J(n) by concavity of ln. As Michael calculated in the video, A(k) = 1/2 * [ ln(k) + ln(k+1) ] = 1/2 * ln( k(k+1) ). I claim now that the *difference* in these areas (which is very closely related to a_n, as we'll see) is less than 1, that is, that J(n) - T(n) ≤ 1 for every n. To do this, consider a second sum of areas, this time larger than J(n). Namely, let B(k) be the area of the trapezoid based on the interval [k,k+1] on the x-axis and whose top edge is tangent to the graph of ln(t) at the midpoint t=k+1/2. Let T(n) = B(1) + ... + B(n-1) be their sum. Since ln is concave, the tangent lines lie above the graph, and so T(n) ≥ J(n) ≥ S(n). Clearly, the area B(k) = ln(k+1/2) = ln( (2k+1)/2 ) = 1/2 * ln( (2k+1)²/4 ) Now we can bound J(n) - S(n). I will use ∑ and ∏ for summation and product, here they always run over k = 1,2,3,...,n-1. (Please forgive my trying to type equations in a youtube comment, I've tried to make it as clean as I can. hopefully no typos.) 0 ≤ J(n) - S(n) ≤ T(n) - S(n) = ∑ [ 1/2 * ln( (2k+1)²/4 ) - 1/2 * ln( k(k+1) ) ] = 1/2 * ∑ ln[ (2k+1)² / (4 * k * (k+1)) ] = 1/2 * ln[ ∏ (2k+1)² / (2k * 2(k+1)) ] = 1/2 * ln[ ∏ (2k+1)/(2k) * (2k+1)/(2k+2) ]. The product appearing in the logarithm in that last expression looks suspiciously the (partial products of the) Wallis product (also appearing in the video), but reciprocated, here with the odds on top and evens in the denominator. Indeed, that's essentially what we have here. Again, keep in mind that this *finite* product is over k = 1,2,...,n-1. ∏ (2k+1)² / (2k * 2(k+1)) = ( 3/2 * 3/4 )( 5/4 * 5/6 )( 7/6 * 7/8 ) ... ( (2n-1)/(2n-2) * (2n-1)/(2n) ) = (2 * 1/2)( 3/2 * 3/4 )( 5/4 * 5/6 )( 7/6 * 7/8 ) ... ( (2n-1)/(2n-2) * (2n-1)/(2n) ) (we merely introduced 2 * 1/2 = 1 at the front) = 2 * ( 1/2 * 3/2 )( 3/4 * 5/4 )( 5/6 * 7/6 ) ... ( (2n-3)/(2n-2) * (2n-1)/(2n-2) ) * (2n-1)/(2n). (regrouping the product to pair the evens) In the last step, we simply regrouped the product (as indicated by the parentheses) to pair up the evens in the bottom (including the 1/2 we introduced in the previous step) instead of the odds in the top. This is fine because its only a *finite* product. Notice that what we're left with is the *reciprocal of the (n-1)-st partial product* of the Wallis product sandwiched by a factor of 2 on the left and (2n-1)/(2n) on the right. Thus, in the limit as n -> ∞, this converges to 2 * 2/π * 1 = 4/π. (Convince yourself that there is no problem switching the reciprocal operation with the limit here.) Summarizing what we've just done, we epressed T(n) - S(n) = 1/2 * ln[ ∏ (...) ] and found that the big product inside the logarithm converges to 4/π as n -> ∞. Since ln is continuous, this means T(n) - S(n) -> 1/2 * ln( 4/π ) as n goes to infinity. But also the sequence T(n) - S(n) is obviously increasing with n (recall this is just the difference between the total area of the first n-1 upper and lower trapezoids, each time n goes up, we just adding the next such difference which is positive). Therefore T(n) - S(n) ≤ 1/2 * ln(4/π) = 0.1207... ≤ 1 for every n. So finally, we have shown that J(n) - S(n) ≤ T(n) - S(n) ≤ 1 for every n. But now we can explicitly calculate J(n) and S(n). It's a easy integration by parts exercise to find J(n) = n * ln(n) - n + 1. For S(n), we find S(n) = A(1) + A(2) + ... + A(n-1) = 1/2 * [ ( ln(1) + ln(2) ) + ( ln(2) + ln(3) ) + ... + ( ln(n-1) + ln(n) ). Notice every term ln(k) for k=2,3,...,n-1 appears exactly twice (canceling the 1/2 out front) execept ln(1) which equals 0 adn the ln(n) at the end. So S(n) = 1/2 * ln(n) + [ ln(2)+ln(3)+...+ln(n-1) ] = 1/2 * ln(n) + ln( 2*3*...*(n-1) ) = 1/2 * ln(n) + ln( (n-1)! ). Putting it all together, 1 ≥ J(n) - S(n) = n*ln(n) - n + 1 - 1/2*ln(n) - ln( (n-1)! ) = 1 + ln[ n^n / (e^n * √n * (n-1)!) ] = 1 - ln[ (e^n * √n * (n-1)!) / n^n ], where we've simply flipped the argument of ln in the last step, picking up a minus sign. So the ln[...] is positive, hence its argument is greater than 1, i.e., 1 ≤ e^n * √n * (n-1)! / n^n = (e/n)^n * n! / √n = a_n. Hooray! The a_n are all ≥ 1, as claimed. So indeed, L ≥ 1 > 0. Hopefully this is readable, I'm limited by the medium here by I've tried to explain all the main steps.

[@franksaved3893]

@@JTISD3LL it's so difficult to read math formulas on KZbin ☹️. But thank you, now we have a lower bound greater than zero!

[@davidvilla9581]

This raises the question of what the limit is of (n!)/(Sqrt(n)*(n/e)^n) as n->infinity. Does it approach one or other of the bounds, or something in between?

[@srikanthtupurani6316]

I like this inequality. It is so beautiful.

[@radadadadee]

24:09 Did you say "...and that's a good place to start?" The video cuts abruptly

[@milanstevic8424]

yes he started the abrupt cut

[@maxhagenauer24]

4:25 Isn't it suppose to be ln( (n+1)^(n+1) / (e * n^n))?

[@GhostyOcean]

Yes, these kinds of mistakes are common in his videos. He uses the correct formula after that though.

[@maxhagenauer24]

@GhostyOcean Yes I think it's because he does a lot of what he writes down by looking at a board or something behind the camera or next to it to know he gets it correct in the end or during the big steps but the smaller steps he tries to do right then and there is where he makes mistakes.

[@goodplacetostop2973]

24:08

[@orionspur]

🛑

[@daboffey]

2 < 2^1 / 1^0 ???

[@ayawwka]

very cool!!

[@Islayyyyyyy]

Happy birthday i know today is your birthday

[@sweetbuns3185]

19:40 cool proof that 2 < e

[@parthhooda3713]

my favorite one is n!≈n!

[@forcelifeforce]

You wasted a post, and your post is reported as spam.

[@ayushmaurya9556]

Ahhh! I see. A very easy way that students can use to estimate the value of 13! 😃 Trivial knowledge to know 7^7 to estimate it.

[@Sam27182]

I don't know if this is a joke or not, but it actually is very useful. Calculating n! is very hard for large n, and in physics you want to know the factorial of numbers on the order of 10^23. However, (10^23/e)^(10^23) is a much easier number to calculate, so the approximation is great. Or, in fact, we usually do the logarithm version that ignores the constant, n*ln(n)-n, which is also very nice to use.

[@forcelifeforce]

@@Sam27182 "the constant, n*ln(n)-n," Again, as long as n is a variable, that is not a "constant."

[@Sam27182]

@@forcelifeforce The constant +1/2ln(2pi) is ignored, leaving nln(n)-n. Well, we also ignore the +1/2ln(n) but you can verify that that for any large n that additional factor is basically irrelevant. With n = 10,000, far below numbers you use the approximation for generally, nln(n) is 92,103 while 1/2ln(n) is 4.6.