0
$\begingroup$

This question already has an answer here:

How do I prove this inequality: $n!>2^n$, where $n\ge 4$. I've searched online but the solutions are vague to me. Thank you! :)

$\endgroup$

marked as duplicate by GNUSupporter 8964民主女神 地下教會, JonMark Perry, Hans Engler, B. Mehta, Wouter May 11 '18 at 8:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Please read your question carefully, I think there might be a typo. $\endgroup$ – David Oct 27 '16 at 2:09
  • $\begingroup$ @David thank you! edited :) $\endgroup$ – Yeol Oct 27 '16 at 2:13
  • $\begingroup$ I changed the hypothesis $n>4$ to $n\ge 4$ since in the case $n=4$ the inequality is also true. $\endgroup$ – Xam Oct 27 '16 at 2:29
  • 1
    $\begingroup$ Instead of searching for solutions online, try to solve it yourself using induction, and explain here where you are stuck so we can help you. $\endgroup$ – user333870 Oct 27 '16 at 2:48
2
$\begingroup$

A proof by induction has three parts: a basis, induction hypothesis, and an inductive step. We show that the basis is true, and then assume that the induction hypothesis is true. We then use our assumption to imply this inequality is true for all other values.

Basis: Let $n=5$. Then $n!=5!=120$. $2^n=2^5=32$. $120>32$.

Induction hypothesis: Suppose $n=k>4$. Assume that $k!>n^k$ holds true.

Inductive: Now let $n=k+1$. $(n+1)!=(n+1)n!$. $2^{k+1}$= $2^k2$. We know $n!>2^k$, so now we must simply compare $n+1$ and $2$. $n$ is strictly greater than $4$, so $n+1$ is certainly greater than $2$. Thus $(n+1)!>2^{k+1}$.

Thus we have shown by induction that $n!>2^k$

$\endgroup$
  • $\begingroup$ does the same idea apply when 2^n instead of n^2? $\endgroup$ – Yeol Oct 27 '16 at 4:02
  • $\begingroup$ Perhaps you mean n^2 instead of 2^n? The same idea for a proof by induction applies to anything you would like to prove by induction, but I can tell you right away that a factorial grows at a much faster rate than an n^2 polynomial and so the inequality will easily hold in that case. $\endgroup$ – zcd29 Oct 27 '16 at 19:31
1
$\begingroup$

We will prove by induction

Base case $n=5$ , $5!=120>32=2^5$

Case $n=k$ assuming true for $n=k-1$

$(k-1)! >2^{(k-1)}$ multiplying by $k$ yields

$k(k-1)! >k*2^{(k-1)}> 2*2^{(k-1)}=2^k$ since $k>2$

$k! >2^k$

$\endgroup$
0
$\begingroup$

Assume $$2^n<n!$$ multiply by $2$ to get $$2^{n+1}<2n!$$ and we see that $$2n!\leq(n+1)n!=(n+1)!$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.