12
$\begingroup$

I know that

$$ \lim_{n\to\infty}{{2n}\choose{n}}^\frac{1}{n} = 4 $$ but I have no Idea how to show that; I think it has something to do with reducing ${n}!$ to $n^n$ in the limit, but don't know how to get there. How might I prove that the limit is four?

$\endgroup$
20
$\begingroup$

Hint: By induction, show that for $n\geq 2$ $$\frac{4^n}{n+1} < \binom{2n}{n} < 4^n.$$

$\endgroup$
  • 1
    $\begingroup$ Better lower bound than mine (+1) $\endgroup$ – robjohn Mar 5 '13 at 1:32
14
$\begingroup$

The term ${2n\choose n}$ occurs as biggest of $2n+1$ positive summands in expanding $(1+1)^{2n}$, which directly shows $\frac{4^n}{2n+1}\le {2n\choose n}\le 4^n$. From this the claim follows by using $\sqrt[n]n\to 1$.

$\endgroup$
  • 1
    $\begingroup$ Simple but effective observation (+1) $\endgroup$ – robjohn Mar 5 '13 at 1:33
  • $\begingroup$ Yes, but it only shows that $0 \le \lim_{n \rightarrow \infty} \binom{2n}{n}^{1/n} \le 4$. $\endgroup$ – vonbrand Mar 5 '13 at 17:31
  • 2
    $\begingroup$ @vonbrand No, it shows $\frac 4{\lim \sqrt[n]{2n+1}}\le \ldots \le 4$, hence equality as required. Note that the well-known $\sqrt[n] n\to 1$ also implies $\sqrt[n] {2n+1}\to 1$. Actually, I just wanted to avoid the big Stirling gun because this "one step" using the immediate defintion of binomial coeffivient works. $\endgroup$ – Hagen von Eitzen Mar 5 '13 at 21:09
  • $\begingroup$ Something is very wrong. My own computation shows the limit is $4 \pi^{-1/8}$, as do other results here. $\endgroup$ – vonbrand Mar 5 '13 at 22:05
  • $\begingroup$ @vonbrand Which limit is $4\pi^{-1/8}$ and which other results here show that? $\endgroup$ – Hagen von Eitzen Mar 5 '13 at 22:20
10
$\begingroup$

Use Stirling formula $$n! \sim \sqrt{2 \pi n} \left(\dfrac{n}e \right)^n$$ This gives us that $$\dbinom{2n}n \sim \dfrac{4^n}{\sqrt{\pi n}}$$ Now conclude that $$\lim_{n \to \infty} \dbinom{2n}n^{1/n} = 4$$

$\endgroup$
  • $\begingroup$ The last step is wrong, you get $4 \pi^{-1/8} \cdot \lim_{n \rightarrow \infty} n^{-1/2 n} = 4 \pi^{-1/8}$ $\endgroup$ – vonbrand Mar 5 '13 at 17:21
  • $\begingroup$ @vonbrand ${{2000}\choose{1000}}^{\frac{1}{1000}} \approx 3.983\ \gt\ 4\pi^{-1/8}$ $\endgroup$ – Jakob Weisblat Mar 5 '13 at 22:12
  • $\begingroup$ @vonbrand the power of $\pi$ is $\pi^{-\frac{1}{2n}}$. $\endgroup$ – TZakrevskiy Aug 22 '13 at 11:11
5
$\begingroup$

Hint: $$ \begin{align} \binom{2n}{n} &=\frac{2n(2n-1)}{n^2}\frac{(2n-2)(2n-3)}{(n-1)^2}\frac{(2n-4)(2n-5)}{(n-2)^2}\cdots\frac{4\cdot3}{2^2}\frac{2\cdot1}{1^2}\\ &=2^n\frac{2n-1}{n}\frac{2n-3}{n-1}\frac{2n-5}{n-2}\cdots\frac{3}{2}\frac{1}{1}\\ &=4^n\frac{n-1/2}{n}\frac{n-3/2}{n-1}\frac{n-5/2}{n-2}\cdots\frac{3/2}{2}\frac{1/2}{1}\tag{1}\\ &\ge4^n\frac{n-1}{n}\frac{n-2}{n-1}\frac{n-3}{n-2}\cdots\frac{1}{2}\cdot1/2\\ &=4^n\frac1{2n}\tag{2} \end{align} $$ $(1)$ and $(2)$ show that $$ \frac1{2n}4^n\le\binom{2n}{n}\le4^n\tag{3} $$

$\endgroup$
3
$\begingroup$

You could use Stirling’s approximation:

$$\lim_{n\to\infty}\frac{n!}{\sqrt{2n\pi}(n/e)^n}=1\;.$$

Then

$$\binom{2n}n=\frac{(2n)!}{n!^2}\approx\frac{\sqrt{4n\pi}(2n/e)^{2n}}{2n\pi(n/e)^{2n}}=\frac{4^n}{\sqrt{n\pi}}\;,$$

so $$\binom{2n}n^{1/n}\approx\frac4{(\pi n)^{1/n}}\;.$$

I’ll let you fill in the details to show that $\approx$ here can be replaced by $\sim$, meaning that the ratio tends to $1$.

$\endgroup$
2
$\begingroup$

If we know1 that for a sequence $(a_n)$ of positive real numbers we have $$\lim_{n\to\infty} \sqrt[n]{a_n} = \lim_{n\to\infty} \frac{a_{n+1}}{a_n},$$ providing the limit on the right hand side exists, we can use this for $a_n=\binom{2n}n$. We get $$\lim_{n\to\infty} \frac{\binom{2n+2}{n+1}}{\binom{2n}n} = \lim_{n\to\infty} \frac{(2n+1)(2n+2)}{(n+1)^2} = 4.$$

Notice that this approach is not that different from taking a logarithm and applying Stolz-Cesaro theorem. (Which is actually a possible way the result about $\sqrt[n]{a_n}$.)


1This result is proved in some other posts on this site, for example: Limit of ${a_n}^{1/n}$ is equal to $\lim_{n\to\infty} a_{n+1}/a_n$, Convergence of Ratio Test implies Convergence of the Root Test, How to show that $\lim_{n \to \infty} a_n^{1/n} = l$?, Elementary way to show $\lim_{n \rightarrow \infty} \sqrt[n]{a_n} = \lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n}$?.

$\endgroup$
1
$\begingroup$

\begin{align} \lim_{n\to\infty}\log\left(\sqrt[n]{2n \choose n}\right)&=\lim_{n\to\infty}\log\left(\sqrt[n]{\frac{2n!}{n!n!}}\right)\\ &=\lim_{n\to\infty}\log\left(\sqrt[n]{\frac{\prod_{k=1}^n(n+k)}{\prod_{k=1}^n k}}\right)\\ &=\lim_{n\to\infty}\frac{\sum_{k=1}^n\log\left(\cfrac{n+k}{k}\right)}{n}\\ &=\lim_{n\to\infty}\frac{\sum_{k=1}^n\log\left(1+\cfrac{n}{k}\right)}{n}\\ &=\int_0^1 \log\left(1+\frac1x\right)dx\\ &=\int_0^1 (\log(1+x)-\log x)dx\\ &=\left[(1+x)\log x(1+x)-x\log x\right]_0^1\\ &=2\log2=\log4\\ \therefore \lim_{n\to\infty}\sqrt[n]{2n \choose n}&=4 \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.