7
$\begingroup$

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

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

  • 4
    How is your function defined for odd $n$? What have you tried? What happens if you increase $n$ by 2?2011-09-25

3 Answers 3

9

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

9

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.

5

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

  • 4
    @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.2011-09-25