Combinatorially showing $\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}=0$

Solution 1:

Not a combinatorial approach, but a fun way of doing it is showing that $$\frac{\binom{2n}{n}}{4^n}=\frac{1}{2\pi}\int_0^{2\pi} \cos^{2n} x\; dx$$

Basically, writing $\cos x = \frac12\left(e^{ix}+e^{-ix}\right)$. So $\cos^{2n} x$ has constant term $\binom{2n}{n}/4^n$.

Since $\cos^{2n} x\to 0$ for almost all $x$, it is pretty easy to show that the above integral tends to zero as $n\to\infty$.
Specifically, on the intervals $(\varepsilon,\pi-\varepsilon)\cup(\pi+\varepsilon,2\pi-\varepsilon)$, $\cos^{2n}x\to 0$ uniformly.

Solution 2:

Here’s a non-combinatorial argument that avoids Stirling’s approximation.

$$\begin{align*} p_n\triangleq\frac{\binom{2n}n}{4^n}&=\frac{(2n)!}{(2^nn!)^2}\\\\ &=\frac{(2n)!(2n-1)!!^2}{(2n)!^2}\\\\ &=\frac{(2n-1)!!^2}{(2n)!}\\\\ &=\prod_{k=1}^n\frac{2k-1}{2k}\\\\ &=\prod_{k=1}^n\left(1-\frac1{2k}\right)\;, \end{align*}$$

so

$$\ln p_n=\sum_{k=1}^n\left(-\sum_{m\ge 1}\frac1{m(2k)^m}\right)\le-\sum_{k=1}^n\frac1{2k}=-\frac12H_n\;,$$

where $H_n$ is the $n$-th harmonic number. The harmonic series diverges, so $\lim_{n\to\infty}\ln p_n=-\infty$, and therefore $\lim_{n\to\infty}p_n=0$.

Note: The double factorial $(2n-1)!!$ is the product of the odd positive integers not exceeding $2n-1$:

$$(2n-1)!!=\prod_{k=1}^n(2k-1)=\frac{(2n)!}{2^nn!}\;.$$