# Limit involving binomial coefficients without Stirling's formula

I have this question from a friend who is taking college admission exam, evaluate: $$\lim_{n\to\infty} \frac{\binom{4n}{2n}}{4^n\binom{2n}{n}}$$ The only way I could do this is by using Stirling's formula:$$n! \sim \sqrt{2 \pi n} (\frac{n}{e})^n$$ after rewriting as $$\lim_{n\to\infty} \frac{(4n)!(n!)^2}{4^n(2n)!^3}$$ and it simplifies really satisfying to $\frac{1}{\sqrt2}$.

However Stirling's formula is not in the syllabus nor taught in high school, is there an elementary approach to this limit?

• I think expecting high student to know more than the syllabus, in order for a college to admit 'good' student, may not be quite surprising... – Tony Ma Apr 1 '18 at 7:56

## 3 Answers

$$l=\lim_{n\to \infty} \frac{(4n)!(n!)^2}{4^n(2n)!^3}=\lim_{n\to\infty}\frac{n!\cdot (2\cdot 2n)(4n-1)(2\cdot (2n-1))...(2n+1)}{2^n2^n(2n)!\cdot (2n)(2n-1)...(n+1)}$$ And with some adjustments results in: $$l=\lim_{n\to \infty}\frac{(2n+1)(2n+3)...(4n-1)}{(2n+2)(2n+4)...(4n)}$$ Taking logarithm on both sides gives: $$\ln l=\lim_{n\to\infty}\sum_{k=1}^{n}ln\left(\frac{2n+2k-1}{2n+2k}\right)$$ And using the fact that $$\displaystyle{\lim_{x\to0} \ln(1+x)=x}$$ we get that: $$\ln l=\lim_{n\to\infty}\sum_{k=1}^{n}\frac{-1}{2n+2k}=-\frac{1}{2}\lim_{n\to\infty} \frac{1}{n}\sum_{k=1}^{n}\frac{1}{1+\frac{k}{n}}$$ Which evaluates as a Riemann sum:$$\ln l=-\frac{1}{2}\int_0^1\frac{1}{1+x}dx=-\frac{1}{2}\ln 2\Rightarrow l=\frac{1}{\sqrt2}$$

Actually you don't even need $\frac{1}{4^n}\binom{2n}{n}\sim\frac{1}{\sqrt{\pi n}}$ which can be proved, for instance, through $$\frac{1}{4^n}\binom{2n}{n}=\frac{2}{\pi}\int_{0}^{\pi/2}\cos(t)^{2n}\,dt \sim \frac{2}{\pi}\int_{0}^{+\infty}e^{-nt^2}\,dt.$$ Here you have to consider $$\lim_{n\to +\infty}\prod_{k=1}^{n}\frac{k\cdot k\cdot(4k-3)\cdot(4k-2)\cdot(4k-1)\cdot 4k}{4\cdot(2k-1)^3\cdot (2k)^3}=\lim_{n\to +\infty}\prod_{k=1}^{n}\left(1-\frac{1}{4(2k-1)^2}\right)$$ and $$\prod_{k\geq 0}\left(1-\frac{1}{4(2k+1)^2}\right) = \lim_{z\to \pi/4}\prod_{k\geq 0}\left(1-\frac{4z^2}{(2k+1)^2\pi^2}\right)=\lim_{z\to \pi/4}\cos(z)=\frac{1}{\sqrt{2}}$$ by the Weierstrass product for the cosine function. Notice that the final outcome ($\frac{1}{\sqrt{2}}$) is unaffected if we know in advance that $\lim_{n\to +\infty}\frac{\sqrt{n}}{4^n}\binom{2n}{n}=C$ for some mysterious and non-explicit constant $C$. By squaring and telescoping, this boils down to the fact that $\prod_{k\geq 1}\left(1-\frac{1}{(2k+1)^2}\right)$ is convergent, which on its turn boils down to the fact that $\sum_{k\geq 1}\frac{1}{(2k+1)^2}$ is convergent.

If you look here, you will see that

"The Wallis product can be written in asymptotic form for the central binomial coefficient"

$${2m \choose m} \sim \frac{4^m}{\sqrt{\pi \,m}}$$

In the same page, they also give useful upper and lower bounds of it.

• that is nice! But is this elementary? I mean do they learn about asymptotics form until college? – Number Apr 1 '18 at 8:30
• Isn't striling formula as 'elementary' as this or even more 'elementarier'? – Tony Ma Apr 1 '18 at 8:33
• @Zacky. I totally agree with you. When I was young (long time ago), this is what we were given for the central binomial coefficient – Claude Leibovici Apr 1 '18 at 8:34
• @TonyMa. It is more "elementary" than Stirling but still ... – Claude Leibovici Apr 1 '18 at 8:36