Combinatorial Limit

Calculus Level 2

lim n ( 2 n n ) 1 n = ? \large \lim_{n \rightarrow \infty} { 2n \choose n } ^ { \frac{1}{n} } = \ ?

e e 3 π \pi 4

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Gautam Sharma
Jul 13, 2015

Another approach O f solving this is by Definite Integration as Limits of sum. But here we can't see any summation .In problems with exponents l n ln is the key.

Let A = lim n ( 2 n n ) 1 / n A= \large \lim_{n \rightarrow \infty} { 2n \choose n } ^ { 1 / n }

Taking l n ln both sides we get l n ( A ) = l n ( lim n ( 2 n n ) 1 / n ) ln(A)= ln( \lim_{n \rightarrow \infty} { 2n \choose n } ^ { 1 / n } ) l n ( A ) = lim n l n ( ( 2 n n ) 1 / n ) ln(A)= \lim_{n \rightarrow \infty}ln( { 2n \choose n } ^ { 1 / n } ) l n ( A ) = lim n 1 n l n ( n + 1 ) ( n + 2 ) . . . ( n + n ) 1.2.3.... n ln(A)= \lim_{n \rightarrow \infty} \frac{1}{n} ln \frac{(n+1)(n+2)...(n+n)}{1.2.3....n} l n ( A ) = lim n 1 n ( l n n + 1 1 + l n n + 2 2 + l n n + 3 3 + . . . . . + l n n + n n ) ln(A)= \lim_{n \rightarrow \infty} \frac{1}{n}( ln \frac{n+1}{1}+ ln \frac{n+2}{2}+ ln \frac{n+3}{3}+.....+ ln \frac{n+n}{n}) l n ( A ) = lim n 1 n r = 1 n l n ( n + r ) r ln(A)= \lim_{n\rightarrow\infty}\frac{1}{n} \sum_{r=1}^{n}ln\frac{(n+r)}{r} l n ( A ) = 0 1 l n ( 1 + x x ) d x ln(A)= \int _{ 0 }^{ 1 }{ ln(\frac { 1+x }{ x } )dx } l n ( A ) = l n ( 4 ) ln(A)= ln(4) A = 4 A=4

Moderator note:

Good observation.

Be careful when interchanging limits and functions. You have to justify why this can be done, like that the limit exists and the function is continuous. As such, there is work that needs to be done first.

I don't understand how you made this limit.

Andrei Cr - 3 years, 1 month ago

Can yo please elaborate the last three steps? I don't get it

Muhsin Al Azeez - 2 years, 5 months ago

Integral of lnx is xlnx-x so ln4-2 , -2 is missing

Bhanu Sri - 1 year ago
Shourya Pandey
Apr 23, 2016

We know that S ( n ) = ( 2 n n ) S(n) = {2n \choose n } is the largest of the n + 1 n+1 binomial coefficients ( 2 n 0 ) 2n \choose 0 , ( 2 n 1 ) 2n \choose 1 ,...., ( 2 n 2 n ) 2n \choose 2n . Also, the sum of all binomial coefficients is 2 2 n = 4 n 2^{2n} = 4^n So 4 n S ( n ) 4 n 2 n + 1 4^n \geq S(n) \geq \frac {4^n}{2n+1} .

Therefore 4 S ( n ) 1 n 4 ( 2 n + 1 ) 1 n 4\geq S(n)^{\frac {1}{n}} \geq \frac {4}{{(2n+1)}^{\frac {1}{n}}} . The squeeze theorem now gives our result, as lim n ( 2 n + 1 ) 1 n = 1 \lim_{n \to \infty} (2n+1)^{\frac {1}{n}} =1 .

+1. This solution is the most elementary and doesn't rely on other 'well-know results'.

Wen Z - 4 years, 9 months ago

Please explain me how can you write (n+1)S > 4^n . @Shourya Pandey

Ankit Kumar Jain - 3 years ago

Log in to reply

I think he meant to write S ( n ) 4 n 2 n + 1 S(n) \geq \frac{4^n}{2n+1} , since there are 2n+1 binomial coefficients. However, the solution still works (e.g., lim n ( 2 n + 1 ) 1 n = 1 \lim_{n \to \infty} (2n+1)^{\frac{1}{n}} = 1 ).

The logic behind the inequality is that if you have A numbers summing up to B, then B is at most A times the largest of the numbers. More discretely, you can write an inequality with a particular member of the A numbers on one side, and the maximum on the other, and then add up all of the inequalities to get the desired result.

Since 2n choose n is the largest of these binomial coefficients, we have the given inequality.

Andre Bourque - 2 years, 12 months ago
Jubayer Nirjhor
Jul 10, 2015

We have ( 2 n n ) = ( 2 n ) ! ( n ! ) 2 \dbinom{2n}{n}=\dfrac{(2n)!}{(n!)^2} . Subbing Stirling and simplifying gives us lim n ( 2 n n ) 1 / n = lim n 4 π 1 / 2 n n 1 / 2 n . \lim_{n\to\infty}\dbinom{2n}{n}^{1/n}=\lim_{n\to\infty}\dfrac{4}{\pi^{1/2n}n^{1/2n}}. As n n approaches infinity π 1 / 2 n \pi^{1/2n} approaches 1 1 . Also n 1 / 2 n n^{1/2n} approaches 1 1 because n n grows linearly while 2 n 2n -th root reduces exponentially. So the answer is 4 \fbox 4 .

Yup. It's a pretty well-known result that ( 2 n n ) = O ( 4 n ) \binom{2n}{n} = O(4^{n}) .

Jake Lai - 5 years, 11 months ago

Log in to reply

but what is O here?????? any thing multiplied by 0 is 0.........is it zero?????

Shumail Hassan - 5 years, 10 months ago

Log in to reply

It is the Big O notation.

Sualeh Asif - 5 years, 2 months ago

The approximation of the central binomial coefficient by { 4 / sqrt (pi n) } as n --> infinity

Harout G. Vartanian - 4 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...