How Do You Calculate the Limit of (2n)!/(4n(n!)^2) as n Approaches Infinity?

[looserlama]

Homework Statement

This is basically just a step in a problem I'm doing, but I can't find a solution for it anywhere.

So, limit as n\rightarrow\infty (2n)!/(4ⁿ(n!)²)

The Attempt at a Solution

I tried writing out the factorials of the top and bottom to see if anything would cancel out, but it doesn't work, at least I don't see how.

I know that it goes to 0, but I don't know how to actually compute it.

Any help at all would be much appreciated.

 

[Dick]

Try a ratio test.

 

[looserlama]

Isn't the ratio test just for series though?

Also, if we are talking about the same ratio test, then that equals 1, so it's inconclusive. That's kind of how I got to this point in my problem.

 

[scurty]

I did a bunch of factoring and rearranging and ended up with 0. I'm almost certain there is an easier way but I didn't see one. I'm hesitant to tell you what I did because there's a good chance I made an error. If you are still stuck I can guide you along with what I did.

Well, I'm pretty sure my first step is valid, I canceled out a n! from top and bottom.

 

[Dick]

Isn't the ratio test just for series though?

Also, if we are talking about the same ratio test, then that equals 1, so it's inconclusive. That's kind of how I got to this point in my problem.

Yeah, you are right. If you can use the ratio test to show a series converges then you know that the terms of the series go to zero. But you are right, it's inconclusive.

 

[scurty]

Disregard my first post. The squeeze theorem works in this case, I'm fairly sure. I found two functions that bound the function in the first post that both converge to 0. I think that's how you would solve this problem?

 

[Dick]

I did a bunch of factoring and rearranging and ended up with 0. I'm almost certain there is an easier way but I didn't see one. I'm hesitant to tell you what I did because there's a good chance I made an error. If you are still stuck I can guide you along with what I did.

Well, I'm pretty sure my first step is valid, I canceled out a n! from top and bottom.

My next approach would be to use Stirling's approximation. The leading terms will cancel. You could just keep adding subleading terms until one doesn't cancel. That's not very easy either. What's your idea?

 

[scurty]

My idea didn't turn out correct, I made a few errors. After you cancel out the n! everything just gets messy.

 

[Dick]

My idea didn't turn out correct, I made a few errors. After you cancel out the n! everything just gets messy.

My first idea didn't work either. Try using Stirling's approximation in the form n! \approx \sqrt{2 \pi n} (\frac{n}{e})^n. The limit is a little delicate. It's the square root term that make the difference.

 

[scurty]

My first idea didn't work either. Try using Stirling's approximation in the form n! \approx \sqrt{2 \pi n} (\frac{n}{e})^n.

That works pretty well, I simplified it down to \displaystyle\frac{1}{\sqrt{\pi}} \cdot \displaystyle\lim_{n \rightarrow \infty} \frac{1}{\sqrt{n}} = 0.

But as I mentioned above, I think the squeeze theorem works as well. I like your way though! Sterling is an upper bound approximation, right? So if all the terms are positive and the approximation approaches 0, the original limit must approach 0, right?

 

[Dick]

That works pretty well, I simplified it down to \displaystyle\frac{1}{\sqrt{\pi}} \cdot \displaystyle\lim_{n \rightarrow \infty} \frac{1}{\sqrt{n}} = 0.

But as I mentioned above, I think the squeeze theorem works as well. I like your way though! Sterling is an upper bound approximation, right? So if all the terms are positive and the approximation approaches 0, the original limit must approach 0, right?

Stirling is an asymptotic approximation. The limit of the approximation over n! goes to one as n goes to infinity. I'm not sure there is any guarantee it's greater or less than n!. I still think this way might be too complicated. What's your idea? I thought you decided it didn't work?

 

[scurty]

My first idea didn't work. My second one I think is pretty conclusive:

Notice:

\displaystyle\frac{(2n)!}{4^{n}((2n)!)^{2}} \leq \displaystyle\frac{(2n)!}{4^{n}(n!)^{2}} \leq \displaystyle\frac{2^{n}(n!)^{2}}{4^{n}(n!)^{2}}.

I think it's pretty obvious why the first inequality holds. The second one is true because (2n)! \leq 2^{n}(n!)^{2}. It's just an algebra exercise but eventually it boils down to
(2n-1)(2n-3)(2n-5)\cdot\cdot\cdot(7)(5)(3)(2) \leq (2n)(2n-2)(2n-3)\cdot\cdot\cdot(6)(4)(2). Both sides have n terms so you just need to match them up in pairs and compare them. The limit of the function all the way on the right approaches 0 as does the left.

Edit: I typoed in the far right equation. Everything is good now.

 

[Dick]

My first idea didn't work. My second one I think is pretty conclusive:

Notice:

\displaystyle\frac{(2n)!}{4^{n}((2n)!)^{2}} \leq \displaystyle\frac{(2n)!}{4^{n}(n!)^{2}} \leq \displaystyle\frac{2^{n}(2n)!}{4^{n}(n!)^{2}}.

I think it's pretty obvious why the first inequality holds. The second one is true because (2n)! \leq 2^{n}(n!)^{2}. It's just an algebra exercise but eventually it boils down to
(2n-1)(2n-3)(2n-5)\cdot\cdot\cdot(7)(5)(3)(2) \leq (2n)(2n-2)(2n-3)\cdot\cdot\cdot(6)(4)(2). Both sides have n terms so you just need to match them up in pairs and compare them. The limit of the function all the way on the right approaches 0 as does the left.

I think if you use Stirling to check the limit of the expression on the right it goes to infinity. That's kind of a nonstarter.

 

[scurty]

Sorry, I made a typo in the equation on the right. How about now? It converges to 0 and is greater than the original equation for all n.

 

[Dick]

Sorry, I made a typo in the equation on the right. How about now? It converges to 0 and is greater than the original equation for all n.

No, I'm still not buying it. 20! is much greater than (2^10)*(10!)^2. As I said the limit is 'delicate'.

 

[scurty]

You're right, sorry. When I got to this step,

(2n)! = (2n)(2n-1)(2n-2)(2n-3)(2n-4)\cdot\cdot\cdot(4)(3)(2)(1)\\

I factored our a single 2 and made it


(2n)! = 2(n)(2n-1)(n-1)(2n-3)(n-2)\cdot\cdot\cdot(2)(3)(1)(1)\\

and then factored out a n! when it should have been

(2n)! = 2^{n}(n)(2n-1)(n-1)(2n-3)(n-2)\cdot\cdot\cdot(2)(3)(1)(1)\\.

Basically I factored out all the 2s from the even terms and wrote it as a single 2 instead of 2^{n}.

Well, back to the drawing board... I never see mistakes in my own work until someone tells me I'm wrong and I go back carefully and then notice it. :/

 

[Dick]

That's ok. Checking with numbers often helps you to find gaffes like this. It's pretty easy if you've got a computer. :) I do it a lot. As should be obvious from my last post.

 

[SammyS]

We haven't heard from OP, looserlama, since post #3.

 

[looserlama]

Yea I've been working on other stuff but I've been following the conversation.

So this is where I'm at now:

We've never seen stirling's approximation before so I don't think we're supposed to use it.
So I've just been focusing on the Squeeze theorem way:

It's easy to show (2n)!/4ⁿ((2n)!)²≤ (2n)!/4ⁿ(n!)²

But finding an upper bounding sequence that goes to zero is the hard part.

What I'm thinking now is, (2n)! = 2ⁿ(n!) [(2n-1)(2n-3)...(3)(1)]
The second part (stuff in square brackets) is ≤ 2ⁿ(n!)

So we have (2n)! ≤ 2ⁿ(n!)2ⁿ(n!) = 4ⁿ(n!)² but if we try to makes this an upper bounding sequence (ie, (2n)!/4ⁿ(n!)² ≤ 4ⁿ(n!)²/4ⁿ(n!)²= 1) then it doesn't converge to 0.

So I wanted to show (2n-1)(2n-3)...(3)(1) ≤ 2ⁿ(n-1)!, I know this is true but I don't know how to prove it.

Cause if we have that, then (2n)!/4ⁿ(n!)² ≤ 4ⁿ(n!)(n-1)!/4ⁿ(n!)²= 1/n which goes to zero.

I just don't know how to prove that?

 

[emailanmol]

Its simple.
Expand
(2n)!
As (2^n)*(n!)*{(2n-1)(2n-3)(2n-5)...5*3*1)}

Now divide this by 4^n*(n!)^2

What do you get??

Its (2n-1)*(2n-3)*(2n-5)...3*1/((2^n)(n!))

There are n terms in numerator .Divide each by 2 to get rid of 2^n

What do you see?

 

[emailanmol]

Also

(2n-1)(2n-3)...(3)(1) ≤ 2^n*(n-1)!

Is not true.
The LHS has n terms giving rise to n^n and RHS has only n-1 terms.

We know that when limit temds to infinity only the highest power factor matters.
So LHS will be greater

 

[looserlama]

Also

(2n-1)(2n-3)...(3)(1) ≤ 2^n*(n-1)!

Is not true.
The LHS has n terms giving rise to n^n and RHS has only n-1 terms.

We know that when limit temds to infinity only the highest power factor matters.
So LHS will be greater

I'm pretty sure that's wrong, just from me computing 2ⁿ(n-1)! - \frac{n!}{n!} = 2ⁿ(n-1)! - (2n-1)(2n-3)...(3)(1) with vary large numbers. For all of them it was always positive and it was increasing as n got larger.

Also, if we try dividing (2n-1)(2n-3)...(3)(1) by 2ⁿ, so dividing each term by 2, gives (n-1/2)(n-3/2)...(3/2)(1/2).

So (2n-1)(2n-3)...(3)(1)/2ⁿ(n!) = (n-1/2)(n-3/2)...(3/2)(1/2)/n!

Here the top one is obviously smaller than the bottom, but how do we prove that it goes to zero with this?

 

[emailanmol]

(2n-1)(2n-3)...(3)(1) ≤ 2^n*(n-1)!

Is not true for n -> infinity.
If u have doubts regarding this you can always plug in the expression into wolfram alpha.


For your second part , each factor of numerator is less than the corresponding denominator.

The maximum value for each expression could be 0.999999...9999 (i.e just less than 1)
That gives u something like (0.999...999)^t where t tends to infinity.(How?)
And we know that will be 0.(Why?)




(Remember you cannot compare coefficients of highest factor in this question to get value of limits as the highest power on both numerator and denominator is n^n.
That rule is valid only for n^a where n is a fixed constant)
That rule only applies while