# Show that ${{2m} \choose {m}} \leq \frac{2^{2m}}{\sqrt{2m}}$.

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.

• Bit of an overkill but if it comes down to it you could always use Stirling's approximation. – aleden May 1 '19 at 14:27
• 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 – Peter Franek May 1 '19 at 14:36

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.

• 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. – jmacmanus May 1 '19 at 17:57

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

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

\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}