# Prove By Induction that $n!>2^n$ [duplicate]

Possible Duplicate:
Proof the inequality $n! \geq 2^n$ by induction

Prove by induction that $n!>2^n$ for all integers $n\ge4$.

I know that I have to start from the basic step, which is to confirm the above for $n=4$, being $4!>2^4$, which equals to $24>16$.

How do I continue though. I do not know how to develop the next step.

Thank you.

-

## marked as duplicate by Byron Schmuland, Benjamin Lim, Asaf Karagila, Willie WongFeb 20 '12 at 12:01

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.

## 5 Answers

Suppose that when n=k (k≥4), we have that k!>2^k.

Now, we have to prove that (k+1)!>2^(k+1) when n=(k+1) (k≥4).

(k+1)! = (k+1)k! > (k+1)2^k    (since k!>2^k)

That implies
(k+1)!>2^k *2      (since (k+1)>2 because of k is greater than or equal to 4)

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

Finally  we may conclusion that n!>2^n for all integers n≥4

-

Here's a suggestion. We have that $(n+1)! = (n+1)n!$ and $2^{n+1} = 2\cdot 2^n$. Then, if we know that $n! > 2^n$, and we multiply $n!$ by $n+1$ and $2^n$ by $2$, can you work out what will happen to the inequality?

-

(i) When $n=4$, we can easily prove that $\frac{4!}{2^{4}}=\frac{24}{16}>1$.

(ii) Suppose that when $n=k$ $(k\geq4)$, we have that $k!>2^{k}$.

(iii) Now, we need to prove when $n=(k+1)$ $(k\geq4)$, we also have $(k+1)!>2^{k+1}$.

We transfer the equation that $\frac{k+1}{2}k!>2^{k}$. As (2), we have known that $k!>2^{k}$, now we only need to prove that $\frac{k+1}{2}>1.0$.

We have known that $k\geq 4$, hence, it easily proves that $\frac{k+1}{2}>1$. In other words, we prove that $(k+1)!>2^{k+1}$.

Thereby, $n!>2^{n}$ for all integers $n\geq 4$. $\square$

-

Hint: prove inductively that a product is $> 1$ if each factor is $>1$. Apply that to the product $$\frac{n!}{2^n}\: =\: \frac{4!}{2^4} \frac{5}2 \frac{6}2 \frac{7}2\: \cdots\:\frac{n}2$$

This is a prototypical example of a proof employing multiplicative telescopy. Notice how much simpler the proof becomes after transforming into a form where the induction is obvious, namely: $\:$ a product is $>1$ if all factors are $>1$. Many inductive proofs reduce to standard inductions.

-

Guide: If $a>b>0$ and $c>d>0$, then we know that $ac>bd$. Now if we know $n!>2^n$ for some positive integer $n$, and we also know that $n+1>2$....

-