1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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}}$ $\endgroup$ – lulu Jun 22 '18 at 0:15
  • $\begingroup$ I must use induction here. $\endgroup$ – SolidSnackDrive Jun 22 '18 at 0:17
  • 1
    $\begingroup$ Seems contrived. But fine, split off the $n!$ as before and apply induction to show that the second factor $>2^n$. $\endgroup$ – lulu Jun 22 '18 at 0:18
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think you may have written one too many 2s $\endgroup$ – SolidSnackDrive Jun 22 '18 at 0:24
  • $\begingroup$ 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. $\endgroup$ – Pelleaon Jun 22 '18 at 0:32
  • $\begingroup$ So it's really my bad, edited for clarity $\endgroup$ – SolidSnackDrive Jun 22 '18 at 0:40
0
$\begingroup$

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

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

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

$\endgroup$
0
$\begingroup$

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.

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

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.