0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Steven Stadnicki Jan 26 '14 at 8:28
  • $\begingroup$ @StevenStadnicki: Why would you post a complete answer as a comment which left us with nothing? $\endgroup$ – Gigili Jan 26 '14 at 8:40
  • $\begingroup$ @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. $\endgroup$ – Steven Stadnicki Jan 26 '14 at 8:45
  • $\begingroup$ @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! $\endgroup$ – Gigili Jan 26 '14 at 8:47
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

$$\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)]!$$

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