# A question about limit $\lim_{n\to\infty} {n \choose n/2}/2^n$

My question is: What is the result of this limit:

$\displaystyle \lim_{n \to +\infty} \frac{{n \choose n/2}}{2^n}=$ ?

-
How is your function defined for odd $n$? What have you tried? What happens if you increase $n$ by 2? – Mark Bennet Sep 25 '11 at 16:10

If you use the Stirling's formula approximation in Wikipedia this decreases as $1/\sqrt{n}$ and goes to $0$.

-

For even $n$, this is the probability that you flip $n$ fair coins and get exact $n/2$ heads.

As shown by the Central Limit Theorem, this binomial distribution can be asymptoticly approximated by a Gaussian distribution of mean $n/2$ and variance $n/4$ for large $n$, and this point will be close to the highest density so $\dfrac{{n \choose n/2}}{2^n} \approx \sqrt{\dfrac{2}{\pi n}}$, which falls towards $0$ as $n$ increases.

-

As $\lim_{n\to+\infty} \frac{1}{2^n} \binom{n}{n/2} = \lim_{n\to+\infty} \frac{1}{4^n} \binom{2n}{n}$, and since for $r(n) = \frac{1}{4^n} \binom{2n}{n}$ the ratio

$$r(n) >0 \land \frac{r(n+1)}{r(n)} = \frac{2n+1}{2(n+1)} < 1 \qquad \forall n \ge 1$$

it follows that $\lim_{n \to \infty} r(n) = 0$ since $r(n)$ monotonically decreases as $n$ grows.

Added: To address the gap in my demonstration pointed out by Henning: $$\begin{eqnarray} r(n) = \frac{1}{4^n} \binom{2n}{n} &=& r(0) \prod_{k=0}^{n-1} \frac{r(k+1)}{r(k)} = \prod_{k=0}^{n-1} \frac{2k+1}{2(k+1)} \\ &=& \prod_{k=0}^{n-1} \left( 1 - \frac{1}{2(k+1)} \right) \le \prod_{k=0}^{n-1} \left( 1 + \frac{1}{2(k+1)} \right)^{-1} \\ &\le& \frac{1}{\sum_{k=0}^{n-1} \frac{1}{2(k+1)}} = \frac{2}{H_n} \end{eqnarray}$$ Thus $0 < r(n) \le \frac{2}{H_n}$ and $\lim_{n\to \infty} r(n) = 0$ follows from $\lim_{n\to\infty} \frac{2}{H_n} = 0$.

-
Is it obvious that "monotonically decreases" implies "has limit 0"? The odd-numbered approximants in the Wallis product for $\pi/2$ also decrease monotonically but have a nonzero limit. – Henning Makholm Sep 25 '11 at 16:14
@Sasha How you get $\lim_{n\to+\infty} \frac{1}{2^n} \binom{n}{n/2} = \lim_{n\to+\infty} \frac{1}{4^n} \binom{2n}{n}$? – Fan Zhang Sep 25 '11 at 16:18
@HenningMakholm Yes, you are correct, it does not imply it. I also have to show that $\log(\frac{r(n+1)}{r(n)}) \sim -\frac{1}{2n} + o(n^{-1})$, so that the product $\prod_{n=1}^\infty r(n)$ converges to zero due to divergence of harmonic series. – Sasha Sep 25 '11 at 16:29
@FanZhang I used $\lim_{n\to \infty} r(n) = \lim_{n \to \infty} r(2n)$, which is true is the limit exists. – Sasha Sep 25 '11 at 16:32
@Sasha: I think it would be more correct to say that the product diverges to zero - a bit of odd-sounding terminology which does turn out to be consistent with other notions of convergence/divergence. – Mark Bennet Sep 25 '11 at 16:39