# To prove the inequality:- $\frac{4^m}{2\sqrt{m}}\le\binom{2m}{m}\le\frac{4^m}{\sqrt{2m+1}}$

Problem Statment:-

Prove:-$$\dfrac{4^m}{2\sqrt{m}}\le\binom{2m}{m}\le\dfrac{4^m}{\sqrt{2m+1}}$$

My Attempt:-

We start with $\binom{2m}{m}$ (well that was obvious), to get

$$\binom{2m}{m}=\dfrac{2^m(2m-1)!!}{m!}$$

Now, since $2^m\cdot(2m-1)!!\lt2^m\cdot2^m\cdot m!\implies \dfrac{2^m\cdot(2m-1)!!}{m!}\lt 4^m$

$$\therefore \binom{2m}{m}=\dfrac{2^m(2m-1)!!}{m!}\lt4^m$$

Also, $$2^m\cdot(2m-1)!!\gt2^m\cdot(2m-2)!!\implies 2^m(2m-1)!!\gt2^m\cdot2^{m-1}\cdot(m-1)!\\ \implies \dfrac{2^m\cdot(2m-1)!!}{m!}\gt\dfrac{4^m}{2m}$$

So, all I got to was $$\dfrac{4^m}{2m}\lt\binom{2m}{m}\lt4^m$$

So, if anyone can suggest me some modifications to my proof to arrive at the final result, or just post a whole different non-induction based proof.

Taking the product of the ratios of the terms gives $$\binom{2n}{n}=\prod_{k=1}^n4\frac{k-1/2}{k}\tag{1}$$ Bernoulli's Inequality says $$\sqrt{\frac{k-1}k}\le\frac{k-1/2}{k}\le\sqrt{\frac{k-1/2}{k+1/2}}\tag{2}$$ Applying $(2)$ to $(1)$, we get $$\frac{4^n}{2\sqrt{n}}\le\binom{2n}{n}\le\frac{4^n}{\sqrt{2n+1}}\tag{3}$$

In this answer, it is shown that $$\frac{4^n}{\sqrt{\pi\left(n+\frac13\right)}}\le\binom{2n}{n}\le\frac{4^n}{\sqrt{\pi\left(n+\frac14\right)}}\tag{4}$$ which is a much tighter estimate.

Hint: Let $a_m={2m\choose m}$. Use the well-known recurrence $$a_1=2, \qquad a_m=(4-2/m) \cdot a_{m-1}.$$

You can use the Stirling formula for the lower bound: $$\binom{2m}{m}=\frac{(2m)!}{(m!)^2}= \frac{\left(\frac{2m}{e}\right)^{2m}\sqrt{2\pi2m}}{\left(\left(\frac{m}{e}\right)^{m}\sqrt{2\pi m}\right)^2}(1+o(1))\ge 2^{2m}\frac{\sqrt{4\pi m}}{2\pi m}=\frac{4^{m}}{\sqrt{\pi m}}\ge\frac{4^{m}}{2\sqrt{m}}.$$

• But this only works if you already know that the $o(1)$-term is nonnegative. – Dominik Dec 25 '16 at 8:39
• The $o(1)$ term is always positive for Stirling's formula. – Laars Helenius Dec 25 '16 at 15:50
• This would be sufficient if you applied the formula only in the numerator - but the problem is the denumerator. – Dominik Dec 25 '16 at 15:54
• Good point. It should probably be $\frac{1}{1+o(1)}$ which is more like $1-o(1)$ when $o(1)$ term is positive. – Laars Helenius Dec 25 '16 at 17:05