# 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?

• Seems like you might be able to use: $$\binom{2n}n = \sum_{k=0}^n \binom{n}{k}^2$$ – Thomas Andrews Jul 2 '13 at 2:17
• There are $\binom{2n}{n}$ binary strings of length $2n$ that have exactly $n$ $1$-bits. There are $2^{2n} = 4^n$ total binary strings of length $2n$. If you could argue combinatorially that the former constitute a vanishing fraction of the latter, you'd have your result. – Austin Mohr Jul 2 '13 at 2:26
• Hi note that you have $n\rightarrow 0$ in your limits – Amr Jul 2 '13 at 2:45
• Stirling's formula in this context is a reflection of a deeper fact, namely the central limit theorem: ${2n \choose k} 4^{-k}$ is the probability that a sum of $2n$ Bernoulli random variables takes the value $k$, and these probabilities are governed by the central limit theorem as $n \to \infty$. The result you want can be interpreted in this light. – Qiaochu Yuan Jul 2 '13 at 3:01
• I think one reason it is hard to do this combinatorially is that the value is $O(1/\sqrt n)$, and $\sqrt{n}$ is hard to make combinatorial. But maybe $\binom{2n}{n}^2$ is easier to show is $O(4^{2n}/n)$? – Thomas Andrews Jul 2 '13 at 3:45

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

• Should define $!!$ somewhere - not everybody is well-versed in its meaning. – Thomas Andrews Jul 2 '13 at 2:43
• This is just the proof of a weak form of Stirlings estimate, but shown in a way that one may not recognize it. It would be equivalent to derive a weak form of Stirlings estimate from first principles and then apply that. – Eric Naslund Jul 2 '13 at 2:44
• @Thomas: Don’t you mean ‘not everybody is well-versed in its meaning!!’ ? :-) – Brian M. Scott Jul 2 '13 at 2:44
• @Eric: Sure, but it still avoids Stirling’s approximation itself and uses tools immediately available to anyone who has had standard freshman calculus and a basic exposure to binomial coefficients. – Brian M. Scott Jul 2 '13 at 2:53

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.

• Actually, my problem was that you are seemingly using Tauber's theorem to conclude the series converges at $x=1$; but that requires that you check a hypothesis which actually implies that the coefficients go to zero. – Mariano Suárez-Álvarez Jul 2 '13 at 3:14
• The last thing you quote is usually stated in books as follows: "If $a_n$ is a sequence of positive monotonically decreasing terms, and $\sum a_n$ converges, then $na_n\to 0$." – Pedro Tamaroff Jul 2 '13 at 3:15
• @MarianoSuárez-Alvarez: Things are simplified significantly when it is monotonic and positive. – Eric Naslund Jul 2 '13 at 3:15
• You are not using Abel's theorem but one of its partial converses. for example, littlewood's theorem as given here – Mariano Suárez-Álvarez Jul 2 '13 at 3:15
• There is a Tauberian theorem that says: "If $a_n\geq 0$ and $\lim\limits_{x\to 1^-}\sum a_n x^n$ exists and is $A$ then $\sum a_n$ exists and is $A$." – Pedro Tamaroff Jul 2 '13 at 3:55

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$)

• (There are of course other ways to prove that random walk on a line eventually hits the origin) – Grigory M Jul 2 '13 at 8:58
• Your first identity is also a key part of this delightful paper: Johan Wästlund, "An Elementary Proof of the Wallis Product Formula for pi", Am. Math. Monthly 114 (10), 2007, pp.914–917. – user21467 Jan 15 '14 at 3:32