10
$\begingroup$

The question is as it is in the title:

Show that

$${{2m} \choose {m}} \leq \frac{2^{2m}}{\sqrt{2m}}$$

for all $m \in \mathbb{N}$.

I've had various attempts at this question but it never seems to lead anywhere fruitful. The hint we have been given is in the question is

Consider the square of the product

$$ \frac{(2m)!}{2^{2m}(m!)^2} = \frac{3 \times 5 \times 7 \times \dots \times (2m-1)}{2 \times 4 \times 6 \times \dots \times (2m)}. $$

From the hint it's not too hard to spot where one would go next - the LHS of the original question is disguised as some cheeky factorials - however induction keeps on failing for me and I'm struggling to see a more direct argument. Any light shed on this problem would be appreciated. I feel like I'm missing something obvious.

Thanks in advance.

$\endgroup$
  • $\begingroup$ Bit of an overkill but if it comes down to it you could always use Stirling's approximation. $\endgroup$ – aleden May 1 '19 at 14:27
  • 1
    $\begingroup$ Hint: I would start with $\frac{1}{2} \frac{2}{3}\ldots \frac{2m-1}{2m} = \frac{1}{2m}$. Decompose the LHS into $AB = \frac{1}{2m}$ where $A$ and $B$ are "similar" and play around with it $\endgroup$ – Peter Franek May 1 '19 at 14:36
6
$\begingroup$

Show the stronger inequality $${{2m} \choose {m}} <\frac{2^{2m}}{\sqrt{2m+1}}.$$ It is true for $m=1$. Induction step: for $m\geq 1$, $$\frac{(2m+2)!}{2^{2m+2}((m+1)!)^2}=\frac{(2m)!}{2^{2m}(m!)^2}\cdot \frac{2m+1}{2m+2}< \frac{1}{\sqrt{2m+1}}\cdot \frac{2m+1}{2m+2}\stackrel{?}{\leq}\frac{1}{\sqrt{2m+3}}.$$ So it remains to prove that $$4m^2+8m+3=(\sqrt{2m+1}\sqrt{2m+3})^2\leq (2m+2)^2=4m^2+8m+4$$ which holds.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Very nice, this is exactly how I approached it initially but it never seemed to work out at the inductive step. It's interesting how a stronger result actually made the proof work. $\endgroup$ – jmacmanus May 1 '19 at 17:57
6
$\begingroup$

Now, $$\tfrac{3\cdot5\cdot...\cdot(2m-1)}{2\cdot4\cdot...\cdot2m}=\sqrt{\tfrac{3(3\cdot5)(5\cdot7)...((2m-3)(2m-1))(2m-1)}{4\cdot4^2\cdot6^2\cdot...\cdot(2m-2)^2\cdot4m^2}}<\sqrt{\frac{3(2m-1)}{16m^2}}<\frac{1}{\sqrt{2m}}.$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

This is an incomplete solution, maybe somebody else can see where to go from here.

Use induction with induction statement

$$P(m): {{2m} \choose {m}}\leq \dfrac{2^{2m}}{\sqrt{2m}}$$

Such that the base $(m=1)$ case is

$$P(1): {{2(1)} \choose {(1)}}\leq \dfrac{2^{2(1)}}{\sqrt{2(1)}}$$

This is easily shown because ${{2}\choose{1}} =2 =\dfrac{2\sqrt{2}}{\sqrt{2}}\leq\dfrac{4}{\sqrt{2}}$ and we know $\sqrt{2}<{2}$. Then, assuming $P(m)$ is true, we must show $P(m+1)$ which states

$$P(m+1): {{2(m+1)} \choose {(m+1)}}\leq \dfrac{2^{2(m+1)}}{\sqrt{2(m+1)}}$$

Start with the left hand side

$$\begin{align} {{2(m+1)} \choose {(m+1)}} &= \dfrac{(2(m+1))!}{(m+1)!(2(m+1)-(m+1))!} \\ &=\dfrac{(2m+2)!}{(m+1)!(m+1)!} \\ &=\dfrac{(2m+2)(2m+1)(2m)!}{(m+1)(m+1)m!m!} \\ &=\dfrac{(2m+2)(2m+1)}{(m+1)(m+1)}\Bigg(\dfrac{(2m)!}{m!m!}\Bigg) \\ &=\dfrac{(2m+2)(2m+1)}{(m+1)(m+1)}{{2m} \choose {m}} \\ &\leq\dfrac{(2m+2)(2m+1)}{(m+1)(m+1)}\dfrac{2^{2m}}{\sqrt{2m}} \\ &=\dfrac{2(m+1)(2m+1)}{(m+1)(m+1)}\dfrac{2^{2m}}{\sqrt{2m}} \\ &=\dfrac{(2m+1)}{(m+1)}\dfrac{2^{2m+1}}{\sqrt{2m}} \end{align}$$

Now, since $m \in \mathbb{N}$, it is obvious that

$$m^2(m +2)>1 \implies 2m^3 + 4m^2 >2 \implies 2m^3 + 4m^2 +2m >2m + 2$$

Then,

$$2m^3 + 4m^2 +2m >2m + 2 \implies (m^2+2m+1)(2m)>2(m+1) \implies (m+1)\sqrt{2m}>\sqrt{2(m+1)}$$

Now, since the denominator is larger, we can say

$$\begin{align} {{2(m+1)} \choose {(m+1)}} &\leq\dfrac{(2m+1)}{(m+1)}\dfrac{2^{2m+1}}{\sqrt{2m}} \\ &\leq(2m+1)\dfrac{2^{2m+1}}{\sqrt{2(m+1)}} \end{align}$$

| cite | improve this answer | |
$\endgroup$

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.