18
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Seems like you might be able to use: $$\binom{2n}n = \sum_{k=0}^n \binom{n}{k}^2$$ $\endgroup$ – Thomas Andrews Jul 2 '13 at 2:17
  • 3
    $\begingroup$ 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. $\endgroup$ – Austin Mohr Jul 2 '13 at 2:26
  • 2
    $\begingroup$ Hi note that you have $n\rightarrow 0$ in your limits $\endgroup$ – Amr Jul 2 '13 at 2:45
  • 4
    $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Jul 2 '13 at 3:01
  • 2
    $\begingroup$ 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)$? $\endgroup$ – Thomas Andrews Jul 2 '13 at 3:45
27
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Should define $!!$ somewhere - not everybody is well-versed in its meaning. $\endgroup$ – Thomas Andrews Jul 2 '13 at 2:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Eric Naslund Jul 2 '13 at 2:44
  • 3
    $\begingroup$ @Thomas: Don’t you mean ‘not everybody is well-versed in its meaning!!’ ? :-) $\endgroup$ – Brian M. Scott Jul 2 '13 at 2:44
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Jul 2 '13 at 2:53
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mariano Suárez-Álvarez Jul 2 '13 at 3:14
  • $\begingroup$ 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$." $\endgroup$ – Pedro Tamaroff Jul 2 '13 at 3:15
  • $\begingroup$ @MarianoSuárez-Alvarez: Things are simplified significantly when it is monotonic and positive. $\endgroup$ – Eric Naslund Jul 2 '13 at 3:15
  • $\begingroup$ You are not using Abel's theorem but one of its partial converses. for example, littlewood's theorem as given here $\endgroup$ – Mariano Suárez-Álvarez Jul 2 '13 at 3:15
  • $\begingroup$ 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$." $\endgroup$ – Pedro Tamaroff Jul 2 '13 at 3:55
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ (There are of course other ways to prove that random walk on a line eventually hits the origin) $\endgroup$ – Grigory M Jul 2 '13 at 8:58
  • $\begingroup$ 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. $\endgroup$ – user21467 Jan 15 '14 at 3:32

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.