Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

share|improve this question
3  
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

3 Answers 3

up vote 8 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
3  
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
2  
@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
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. –  Mark Bennet Sep 25 '11 at 16:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.