Show by mathematical induction that $(2n)! > 2^n*n!$ for all $n \geq 2$

Very stuck on this question. Here is what I have attempted.

Base case: $(2*2)! > 2^2*2!$ = $24>8$ Which is true

Hypothesis: Assume for some int k>2 that $(2k)!>2^k*k!$

Then for my inductive step, I am getting stuck. I tried,

$(2(k+1))! > 2^{k+1} *(k+1)!$

$(2k+2)!> 2^{k+1} *(k+1)!$

$(2k+2)(2k+1)(2k)!>2* 2^{k} *(k+1)!$

And then I'm stuck... I understand I am supposed to use my IH somewhere, but I do not understand how to effectively apply it in this step. Can somebody clearly show me how I should use the IH?

• Induction? Much easier to just note that $(2n)!=\overbrace {1\times \cdots \times n}^{\text {= n!}}\times \overbrace {(n+1)\times \cdots \times (2n)}^{\text {n terms}}$ – lulu Jun 22 '18 at 0:15
• I must use induction here. – SolidSnackDrive Jun 22 '18 at 0:17
• Seems contrived. But fine, split off the $n!$ as before and apply induction to show that the second factor $>2^n$. – lulu Jun 22 '18 at 0:18

$$(2(k+1))! \overset{?}{>} 2^{k+1}(k+1)!$$

$$(2k+2)(2k+1)(2k)! \overset{?}{>} \cdot2^{k+1}(k+1)!$$

$$(2k+2)(2k+1)(2k)! \overset{?}{>} 2 \cdot2^k(k+1)k!$$

Now use your IH, since $(2k)! > 2\cdot2^k k!$, you just need to show that

$$(2k+2)(2k+1) > (k+1),$$

which is obvious.

• I think you may have written one too many 2s – SolidSnackDrive Jun 22 '18 at 0:24
• You are right, my bad, I was rewriting your 3rd line which said $(2k)!>2^k∗2k!$ with an extra 2, instead of looking at the title. – Pelleaon Jun 22 '18 at 0:32
• So it's really my bad, edited for clarity – SolidSnackDrive Jun 22 '18 at 0:40

You're almost there: \begin{align} (2(k+1))! &= (2k+2)(2k+1)(2k)! \\ &> (2k+2)(2k+1) 2^k k! \quad \text{(by the induction hypothesis)}\\ &= 2(k+1)(2k+1) 2^k k! \\ &= (2k+1) 2^{k+1} (k+1)! \\ &> 2^{k+1} (k+1)! \end{align}

Without induction: $$(2n)! = (1 \cdot 2 \cdots n) \cdot ((n+1) \cdots (2n)) > n! \cdot (2 \cdots 2) = 2^n \, n!$$

• Isn't induction 'undercover' anyway, when extending $a < b \Rightarrow ca < cb$ for $c >0$ to arbitrary (finite) products? – Guido A. Jun 22 '18 at 0:21
• @GuidoA., sure. – lhf Jun 22 '18 at 0:21
• This style of inductive step confuses me. Where does the right hand side of the inequality come from? – SolidSnackDrive Jun 22 '18 at 0:22
• @SolidSnackDrive, it's the induction hypothesis: $(2k)!>2^k k!$. – lhf Jun 22 '18 at 0:23

We need to show $$(2k+2)(2k+1)(2k)!>2* 2^{k} *(k+1)!$$

We know that $$(2k)!>2^k*k!$$

Thus $$(2k+2)(2k+1)(2k)!> (2k+2)(2k+1)2^k*k!>2^{k+1}*(k+1)!$$

Using induction, you get

$$(2k+2)(2k+1)(2k)! = 2(k+1)(2k+1)(2k)! >$$

$$> 2 \cdot 2^k \cdot (k+1)(k)!$$

Dividing both sides by $2(k+1)$ you are left with

$$(2k+1)(2k)! > 2^k(k)!$$

Using that $2k+1 \geq 1$ it the follows from your induction hypothesis.

• Damn, I knew there was no way I could get in first writing on this tablet haha – John Samples Jun 22 '18 at 0:27