# How to show $((k+1)!)^2 2^k \leq (2(k+1))!$

How do you show that

$((k+1)!)^2 2^{k+1} \leq (2(k+1))!$

This is part of an induction proof and I have not made any progress.

• Remove a factor of $(k+1)!$ from both sides first, so you're left with $2^k (k+1)!\leq (k+2)(k+3)\cdots(2k+2)$; now show that $2\cdot i \leq k+1+i$ for all $i$ from $1$ through $k+1$, and multiply all these inequalities together. – Steven Stadnicki Jan 26 '14 at 8:28
• @StevenStadnicki: Why would you post a complete answer as a comment which left us with nothing? – Gigili Jan 26 '14 at 8:40
• @Gigili In this case, because I didn't think there was enough content to be an answer and because the problem is so simple that there's very little point in hinting. – Steven Stadnicki Jan 26 '14 at 8:45
• @StevenStadnicki: Right, but your comment is a thorough answer as it stands. You could post it as an answer and ... Ta-Da! The problem is solved! – Gigili Jan 26 '14 at 8:47

There is a small discrepancy between the inequality in the title and what's asked for in the text -- one has $2^k$, the other has $2^{k+1}$ on the left hand side -- but both are true, so let's tackle the stronger one. It can be done by straightforward induction.
After checking a base case (either $k=0$ or $k=1$), assume that it's true for $k-1$, i.e., $(k!)^22^k\le(2k)!$. Then
\begin{align} ((k+1)!)^22^{k+1}&=2(k+1)^2(k!)^22^k\\ &\le2(k+1)^2(2k)!\quad\text{by the inductive hypothesis}\\ &=(2k+2)(k+1)(2k)!\\ &\le(2k+2)(2k+1)(2k)!\quad\text{since }k\le2k\\ &=(2k+2)!\\ &=(2(k+1))! \end{align}
$i\leq 2i-1$, so $$((k+1)!)^2 2^{k+1}=(k+1)!(2\cdot 4\cdot\dotsb (2k+2)) =(\prod_{i=1}^{k+1} i)(2\cdot 4\cdot\dotsb (2k+2))\\ \leq (\prod_{i=1}^{k+1} (2i-1))(2k+2)!! =(2k+1)!!(2k+2)!! = (2(k+1))!$$
$$\frac{[2(k+1)]!}{[(k+1)!]^2}=\binom{2(k+1)}{k+1}=\sum_{i=0}^{k+1} \binom{k+1}{i}^2 \geq \sum_{i=0}^{k+1} \binom{k+1}{i} = 2^{k+1}$$ So: $$[(k+1)!]^22^{k+1} \leq [2(k+1)]!$$