8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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