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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.