Proving an inequality involving factorials: $\frac{1}{2\sqrt{n}}\le \frac{(2n)!}{(n!)^2}\cdot\frac{1}{2^{2n}}\le\frac{1}{\sqrt{2n+1}}$

Question

I had a problem in probability and I've solved the first part. For the second part I need to prove the inequalities :

$$\frac{1}{2\sqrt{n}}\le \frac{(2n)!}{(n!)^2}\cdot\frac{1}{2^{2n}}\le\frac{1}{\sqrt{2n+1}}$$

I tried using Stirling's formula but it looks too complicated in the end. Any help would be appreciated.

Answer 1

Let's see:

$(2n!) = \prod\limits_{k=1..2n;n \text{even}}k*\prod\limits_{k=1...2; n\text{ odd}}k=\prod\limits_{k=1..n}2k\prod\limits_{k=1...2n; n\text{ odd}}k=2^n*n!*\prod\limits_{k=1...2n; n\text{ odd}}k$

So $\frac {(2n)!}{(n!)^2}\cdot \frac 1{2^{2n}} = \frac {\prod\limits_{k=1...2n; n\text{ odd}}k}{n!}*\frac 1{2^n}=\frac {\prod\limits_{k=1...2n; n\text{ odd}}k}{\prod\limits_{k=1...2n; n\text{ even}}k}=\prod\limits_{k=1}^n \frac {2k-1}{2k}$

This becomes $\frac 1{2\sqrt{n}} \le \prod\limits_{k=1}^n \frac {2k-1}{2k} \le \frac 1{\sqrt{2n+1}}$ or $\sqrt{2n+1} \le \prod\limits_{k=1}^n \frac {2k}{2k-1} \le 2\sqrt{n}$. Or $2n+1 \le \prod\limits_{k=1}^n \frac {4k^2}{(2k-1)^2}\le 4n$... which we can probably do by induction.

For $n=1$ then $3 \le 4 \le 4$

If true for $n=k$ then

$2k+1\le \prod\limits_{j=1}^k\frac {4j^2}{(2j-1)^2} \le4k$

$(2k+1)*\frac{4(k+1)^2}{(2k+1)^2}\le \prod\limits_{j=1}^{k+1}\frac {4j^2}{(2j-1)^2} \le 4k*\frac{4(k+1)^2}{(2k+1)^2}$

And $(2k+1)*\frac{4(k+1)^2}{(2k+1)^2}= (2k+1)*\frac {4k^2 + 8k + 4}{4k^2 + 4k+1}=(2k+1)(1 + \frac {4k+3}{4k^2 + 4k + 1})$

$= 2k+ 1 + \frac {2k(4k+3) + 4k+3}{4k^2 + 4k + 1}=2k+1 + \frac {8k^2 + 10k + 3}{4k^2 + 4k + 1}>2k+1 + 2 = 2(k+1) + 1$

while $4k*\frac{4(k+1)^2}{(2k+1)^2} =4k*\frac {4k^2 + 8k + 4}{4k^2 + 4k + 1} = 4k(1 + \frac {4k+3}{4k^2 + 4k + 1})=4k + \frac {16k^2 + 12k}{4k^2 + 4k +1} < 4k + \frac {16k^2 + 16k + 4}{4k^2 + 4k + 1} = 4(k+1)$

So... it is true (with equality only holding on the left side for $n=1$... which makes me a little uneasy).

Obviously this is not what they intended. But it works. I assume they wanted something to do with $\sqrt{2n + 1} = \sqrt{(n+1)^2 - n^2}$ but ... I couldn't seem to work that in.

Oh.... $\sqrt{2n + 1}=\sqrt{(n+1)^2 - n^2} = \sqrt{(n-1)(n+1)}< \sqrt{n^2} = n$. Maybe you can work that in. Well... I don't know.

Answer 2

It can be solved directly by induction.

Note that $$ (n!)^22^{2n}=(2\cdot 4\cdot 6 \cdot\cdots \cdot 2n)^2, $$ the middle expression can be rewritten as $$ \prod_{k=1}^n\left(1-\frac{1}{2k}\right). $$ By indcution, for the right inequality, it suffices to show that $$ \frac{1}{\sqrt{2n+1}}\frac{2n+1}{2n+2}<\frac{1}{\sqrt{2n+3}}. $$ This is equivalent to $$ (2n+1)(2n+3)<(2n+2)^2, $$which is trivial.

For the left inequality, it suffices to show that $$ \frac{1}{2\sqrt{n}}\frac{2n+1}{2n+2}>\frac{1}{2\sqrt{n+1}}. $$ This is equivalent to $$ (2n+1)^2>2n(2n+2), $$which is also trivial.

Answer 3

$$\begin{eqnarray*}\frac{1}{4^n}\binom{2n}{n}=\prod_{k=1}^{n}\left(1-\frac{1}{2k}\right)&=&\sqrt{\frac{1}{4}\prod_{k=2}^{n}\left(1-\frac{1}{k}\right)\prod_{k=2}^{n}\left(1+\frac{1}{4k(k-1)}\right)}\\&=&\frac{1}{2\sqrt{n}}\sqrt{\prod_{k=2}^{n}\left(1-\frac{1}{(2k-1)^2}\right)^{-1}}\\(\text{Wallis product})\quad&=&\frac{1}{\sqrt{\pi n}}\sqrt{\prod_{k>n}\left(1+\frac{1}{4k(k+1)}\right)^{-1}}\end{eqnarray*}$$ is trivially $\leq\frac{1}{\sqrt{\pi n}}$ but also $$\begin{eqnarray*}\phantom{\frac{1}{4^n}\binom{2n}{n}aaaaaaaaa}&\geq &\frac{1}{\sqrt{\pi n}}\sqrt{\prod_{k>n}\exp\left(\frac{1}{4(k+1)}-\frac{1}{4k}\right)}\\(\text{Telescopic})\quad&=&\frac{1}{\sqrt{\pi n\exp\frac{1}{4n}}}\end{eqnarray*}$$ and the double inequality can be improved up to: $$\boxed{ \frac{1}{\sqrt{\pi\left(n+\frac{1}{3}\right)}}\leq\frac{1}{4^n}\binom{2n}{n}\leq\frac{1}{\sqrt{\pi\left(n+\frac{1}{4}\right)}}.}$$