Prove by induction that $n!>2^n$

Question

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.

Answer 1

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 \cdot 2$ (since $(k+1)>2$ because of $k$ is greater than or equal to $4$)

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

Finally, we may conclude that $n!>2^n$ for all integers $n≥4$

Answer 2

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?

Answer 3

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

Answer 4

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.

Answer 5

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