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

I am trying to show that $\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}=0$. I found that using stirling’s approximation, I can get:
$$\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}= \lim_{n\to \infty}{\frac{(2n)!}{n!^2*2^{2n}}}= \lim_{n\to \infty}{\frac{(\frac{2n}{e})^{2n}\sqrt{2\pi (2n)}}{((\frac{n}{e})^n\sqrt{2\pi n})^2*2^{2n}}} =\lim_{n\to \infty}{\frac{2\sqrt{\pi n}}{2\pi n}} =0$$

But this seems inelegant where there should be a more elegant, combinatorial proof. Is there an easier way?

#### Solutions Collecting From Web of "Combinatorially showing $\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}=0$"

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.

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!}\;.$$

Another was is to use the generating function of the central binomial coefficients, that is $$\frac{1}{\sqrt{1-x}}=\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{4^{n}}x^{n}.$$ We will make use of the fact that $x_{n}=\binom{2n}{n}\frac{1}{4^{n}}$ is a monotically decreasing sequence to make sure there are no oscillations. It is monotonic since $$x_{n+1}=\binom{2n}{n}\frac{1}{4^{n}}\frac{(2n+2)(2n+1)}{4\left(n+1\right)^{2}}=x_{n}\left(1-\frac{1}{2n+2}\right).$$ Taking the indefinite integral of both sides of the generating function, we have that for $|x|<1,$ $$2-2\sqrt{1-x}=\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{4^{n}}\frac{x^{n+1}}{n+1}.$$ Now, the left hand side converges as $x\rightarrow1$ from the left, and so, since the series has strictly positive coefficients, the right hand side must converge as well. This implies that $$\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{4^{n}}\frac{1}{n+1}$$ is a convergent series, and since the coefficients $\binom{2n}{n}\frac{1}{4^{n}}$ are monotonically decreasing, the divergence of the harmonic series implies that we must have $$\binom{2n}{n}\frac{1}{4^{n}}\rightarrow0.$$

Added Details: Based on the comments, I thought I would give a precise proof of why the series must converge, without appealing to Littlewood’s Tauberian theorem. The proof only requires that the coefficients of the power series, $a_n$, are nonnegative. Let $a_n\geq0$, $s_m=\sum_{n=0}^m a_n$ be the partial sums, and suppose that $\sum_{n=0}^{\infty}a_{n}x^{n}\leq C$ for all $x\in(0,1),$ for some positive constant $C$. Then for $x\in(0,1),$ $$s_{m}=\sum_{n=0}^{m}a_{n}\left(1-x^{n}\right)+\sum_{n=0}^{m}a_{n}x^{n}$$ $$\leq(1-x)\sum_{n=0}^{m}a_{n}\left(1+x+\cdots+x^{n-1}\right)+C$$

$$\leq(1-x)\sum_{n=0}^{m}na_{n}+C.$$ Taking $x$ sufficiently close to $1$, we can make $(1-x)\sum_{n=0}^{m}na_{n}\leq 1$, and so it follows that $s_{m}\leq C+1.$ This means that $s_m$ is monotonically increasing and bounded, its limit, $\sum_{n=0}^\infty a_n$ must converge. In particular, our series $$\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{4^{n}(n+1)},$$ is convergent.

Here is what I think “a combinatorial approach:” Note that $\binom{2n}{n}$ is the number of $n$ element subsets of a $2n$ element set. Consider the quantities $\binom{2n}{n+i},\,i=1,\ldots,k$ for some small $k$ (relative to $n$). We have the relationship $\binom{2n}{n+1} = \frac{n}{n+1}\binom{2n}{n}$, and in general, $\binom{2n}{n+k} = \frac{n-k+1}{n+k}\binom{2n}{n+k-1}$. Now for any $k$, we can choose $n$ so large that $\frac{n-k+1}{n+k}$ is at least $1-\frac{1}{2k}$. This gives us the estimate $\binom{2n}{n+k} \geq (1-\frac{1}{2k})\binom{2n}{n+k-1} \geq \cdots \geq (1-\frac{1}{2k})^k\binom{2n}{n} \geq \frac{1}{2}\binom{2n}{n}$. Therefore, for any $i\in\{1,\ldots,k\}$ and when $n$ is large enough, the number of $n+i$ element subsets of a $2n$ element set is at least $\frac{1}{2}\binom{2n}{n}$. Hence, $\frac{k}{2}\binom{2n}{n} \leq 4^n$. Now, let $k\rightarrow\infty$.

Speaking of combinatorial proofs,
$$\sum_{k=0}^n\frac{\binom{2k}{k}}{2^{2k}}\frac{\binom{2(n-k)}{n-k}}{2^{2(n-k)}}=1.$$
The key step of a combinatorial proof is that $p_k=\binom{2k}k2^{-2k}$ is the probability that random path with $2k$ steps $(1,1)$ and $(1,-1)$ doesn’t touch $x$-axis after the start. So now we see that sequence $p_k$ is monotonic.
But then the first identity obviously implies $p_k\to0$ (if $\forall k\;p_k\gt\epsilon$, $1=\sum p_kp_{N-k}\gt N\epsilon\gt1$)