Intereting Posts

How else can we be nauty?
Prove that $6$ divides $n(n + 1)(n + 2)$
Question on (Semi) Prime Counting Functions
Does upper limit and lower limit exist for any sequence in $\mathbb{R}$?
If $|G|=p^nq$, then $G$ contains a unique normal subgroup of index $q$
Is the absolute value function a linear function?
Square covered with tiles
Improper integral of $\frac{x}{e^{x}+1}$
Find the distance between two lines
The Tuesday Birthday Problem – why does the probability change when the father specifies the birthday of a son?
A diagram which is not the torus
Substitution $x=\sinh(\theta)$ and $y=\cosh(\theta)$ to $(1+x^{2})y'-2xy=(1+x^{2})^{2}$?
Value of $u(0)$ of the Dirichlet problem for the Poisson equation
How to derive the proximal operator of the Euclidian norm?
$\operatorname{func}(f)\to((x,y)\in f\to f(x)=y) $ and $\operatorname{func}(f)\to((x \in \operatorname{dom}(f) \wedge f(x)=y)\to (x,y)\in f)$

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)

- How is $\lim_{x \to a}\left(\frac{x^n - a^n}{x - a}\right) = n\times a^{n-1}$?
- Prove $\binom{2p+1}{p}\equiv2$ mod $p$ when $p$ is any prime.
- The value of $\mathop{\sum\sum}_{0\leq i< j\leq n}(-1)^{i-j+1}\binom{n}{i}\binom{n}{j}$
- Expressing a factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?
- Is there a direct proof of this lcm identity?
- Is this combinatorial identity a special case of Saalschutz's theroem?

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

- Ways to fill a $n\times n$ square with $1\times 1$ squares and $1\times 2$ rectangles
- Number of non-negative solutions of an equation with restrictions
- What does a binomial coefficient with commas mean?
- The number of (non-equal) forests on the vertex set V = {1, 2, …,n} that contains exactly 2 connected components is given by
- Proof of $\sum_{0 \le k \le a} {a \choose k} {b \choose k} = {a+b \choose a}$
- How many passwords can be formed from this maze?
- Induction proof concerning a sum of binomial coefficients: $\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$
- A factorization problem involving Fibonacci and Lucas Polynomials
- Fixed sum of combinations
- “Binomial theorem”-like identities

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.

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.

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.

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.

- Bounded linear operator on a Hilbert space
- What is $ \lim_{n\to\infty}\frac{1}{e^n}\Bigl(1+\frac1n\Bigr)^{n^2}$?
- Finding Divisibility of Sequence of Numbers Generated Recursively
- How do I find roots of a single-variate polynomials whose integers coefficients are symmetric wrt their respective powers
- Sylow 2-subgroups of the group $\mathrm{PSL}(2,q)$
- Are Monotone functions Borel Measurable?
- What is the new probability density function by generating a random number by taking the reciprocal of a uniformly random number between 0 and 1?
- Weak convergence of a sequence of characteristic functions
- Does there exist a field which has infinitely many subfields?
- Is the metric induced by convergence in probability (Ky Fan metric) complete?
- How can I use residue theory to verify this integral formula?
- How many ways to distribute $k$ indistinguishable balls over $m$ of $n$ distinguishable bins of finite capacity $l$?
- Deriving Fourier inversion formula from Fourier series
- Wanted: example of an increasing sequence of $\sigma$-fields whose union is not a $\sigma$-field
- Cross Ratio is positive real if four points on a circle