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.

For every even positive number $N$ we have:

$$ {2N \choose N } < 2^N {N \choose N/2 } < 2 {2N \choose N } $$

(Furthermore, $\frac{2^N {N \choose N/2 }}{{2N \choose N }} \to \sqrt{2} $ for large $N$; i.e., the middle expression tends to the geometric mean of those lower-upper bounds)

I'm interested in some simple proof (perhaps some visual/combinatorial one, perhaps counting paths?) of that pair of inequalities.

share|improve this question

4 Answers 4

up vote 7 down vote accepted

For the first one, note that choosing $n$ elements of $\{1,\dots, 2n\}$ is equivalent to taking a subset of $\{1, \dots, n\}$, and then choosing enough elements from $\{n+1, \dots, 2n\}$ to get exactly $n$. At the first step we have $2^n$ choices, and at the second step we have at most ${n \choose \lfloor n/2 \rfloor}$ choices, hence ${2n \choose n} <2^n{n \choose \lfloor n/2 \rfloor}$.

In formulas, this reads:

$${2n \choose n} = \sum_{k=0}^n{n\choose k}^2 \leq {n\choose \lfloor n/2 \rfloor}\sum_{k=0}^n {n\choose k} = 2^n {n\choose \lfloor n/2 \rfloor}.$$

I'm not immediately sure how to get the second part of the inequality in a similar fashion.

share|improve this answer

Here is another approach to the easy problem (the left inequality). It is tempting to divide by $2^{2N}$. We then are trying to prove that $$\frac{1}{2^{2N}}\binom{2N}{N} <\frac{1}{2^N} \binom{N}{N/2},$$ (or is this where the problem came from?) So we are trying to prove that if we toss a fair coin $2N$ times, the probability of a tie between heads and tails is less than the probability of a tie if we toss the coin $N$ times. This is intuitively clear. And if it is clear, it must be easy to prove.

Indeed something much stronger is true. If we toss a fair coin $2n$ times, the probability of a tie is less than the probability of a tie if we toss the coin $2n-2$ times. Then start with $n=2N$, conclude that the probability of a tie is less than with $n=2N-2$, which is less than the probability with $n=2N-4$, and so on down to $n=N$.

So now we show that the probability of a tie with $2n$ tosses is less than the probability of a tie with $2n-2$ tosses. This is an easy calculation. If we don't want to calculate, note that we have a tie after $2n$ tosses if (i) we have a tie after $n-2$ tosses and the next two tosses split between heads and tails, or if (ii) after $2n-2$ tosses we have two extra heads, and finally get tail, tail, or if (iii) after $2n-2$ tosses we have two extra tails, and finally get head, head.

Since the central binomial coefficient is always the biggest, the sum of the probabilities of (ii) and (iii) is less than the probability of (i). This gives the desired result.

Unfortunately, it seems harder to find a quick intuitive justification for the inequality on the right.

share|improve this answer

It seems that nobody else has proved the upper inequality, so I'll give a couple (nonvisual, noncombinatorial, debatably simple) proofs. In both I'll prove the slightly stronger inequality $$ 2^n \binom{n}{n/2} < \binom{2n+1}{n} $$ which implies the desired one because $\binom{2n+1}{n} = \frac{2n+1}{n+1}\binom{2n}{n} < 2\binom{2n}{n}$.

First proof: This proof actually gives both inequalities at once. First note that $$\begin{aligned} &(n+1)(n+2)(n+3)(n+4)\dotsm (n+n-1)(n+n) \\ &< (n+2)(n+2)(n+4)(n+4)\dotsm (n+n)(n+n) \\ &< (n+2)(n+3)(n+4)(n+5)\dotsm (n+n)(n+n+1) \end{aligned}$$ In other words, $$ \frac{(2n)!}{n!} < 2^n \left(\frac{n!}{\frac n2!}\right)^2 <\frac{(2n+1)!}{(n+1)!} $$ Dividing by $n!$ yields $$ \binom{2n}{n} < 2^n \binom{n}{n/2} < \binom{2n+1}{n} $$

(That proof is, I think, the "standard" one. If you take logs in those initial inequalities and try to estimate the resulting sums by integrals, you're on the road to proving Stirling's formula and Wallis's product and all that. See Gowers' blog, for example.)

Second proof: This one is a little silly. By the AM/GM inequality, if $0<t<1$ then $$ \sqrt{t(1-t)} \le \frac12 $$ and so $$ 2t(1-t) \le t^{1/2} (1-t)^{1/2} $$ Raising both sides to the power $n$ and integrating over $[0,1]$ yields $$ 2^n B(n+1,n+1) \le B(\tfrac n2+1,\tfrac n2+1) $$ where $B(\cdot,\cdot)$ is the Beta function. In other words, $$ \frac{2^n}{(2n+1)\binom{2n}{n}} \le \frac{1}{(n+1)\binom{n}{n/2}} $$ Rearranging yields the desired inequality.

share|improve this answer

This is not quite simple, but here is my approach for the asymptotic formula. It's too long as a comment so I've posted it as an answer, but it is not complete. Perhaps someone can shed light on how to finish this.

$$\frac{2^{n} {N\choose\lfloor\frac{N}{2}\rfloor}}{{2N\choose N}}=2^n\frac{N!}{\lfloor\frac{N}{2}\rfloor!\left(N-\lfloor\frac{N}{2}\rfloor\right)!}\cdot\frac{N!N!}{\left(2N\right)!}$$

$$=2^N\cdot\frac{\left(N\cdot N-1\cdots \lfloor\frac{N}{2}\rfloor+1\right)\left(N\cdot N-1\cdots \lceil\frac{N}{2}\rceil+1\right)}{(2N)\cdot (2N-1)\cdots (N+1)}$$

we can split off this product, but we have to do so a bit differently for $N$ even and $N$ odd. Suppose first $N$ is even, then this expression becomes

$$=2^N\cdot\frac{(N)\cdot (N-1)\cdots(\frac{N}{2}+1)}{(2N)\cdot (2N-2)\cdots (N+2)}\cdot\frac{(N)\cdot (N-1)\cdots(\frac{N}{2}+1)}{(2N-1)\cdot (2N-3) \cdots (N+1)}$$

$$=2^N\cdot\frac{1}{2^{\frac{N}{2}}}\cdot\frac{1}{2^{\frac{N}{2}}}\prod^{N}_{k=\frac{N}{2}+1}\left(1 - \frac{1}{2k}\right)^{-1}$$

$$=\prod^{N}_{k=\frac{N}{2}+1}\left(1 - \frac{1}{2k}\right)^{-1}$$

analogously for odd $N$, we end up with

$$=\prod_{k=\frac{N+1}{2}+1}^{N}\left(1 - \frac{1}{2k}\right)^{-1}$$

In particular, if anyone can find a closed form solution for

$$P=\prod_{k=1}^{n}\left(1 - \frac{1}{2k}\right)$$

then we can prove the asymptotic bound. I am not sure if such an expression exists or not, but I am unsure of how to proceed as of now.

share|improve this answer
    
Tools from a traditional proof of Stirling's formula yield $4^n/\sqrt{\pi(n+1/2)} \le \binom{2n}{n} \le 4^n/\sqrt{\pi n}$ (e.g., Prop 6 here); applying that for $n$ and $n/2$ yields $\sqrt{2-\frac{2}{n+1}}\binom{2n}{n}\le 2^n\binom{n}{n/2}\le \sqrt{2+\frac1n}\binom{2n}{n}$. –  Steven Taschuk Dec 5 '13 at 17:03

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.