# Proof the inequality $n! \geq 2^n$ by induction

I'm having difficulity solving an exercise in my course.

The question is:

Prove that $n!\geq 2^n$.

We have to do this with induction. I started like this:

1. The lowest natural number where the assumption is correct is $4$ as: $4! \geq 2^4 \iff 24 \ge 16$.
2. The assumption is: $n! \ge 2^n$.

Now proof for $(n+1)$ which brings me to: $(n+1)! \ge 2^{(n+1)}$

I think I can rewrite it somehow like this:

$${(n+1)} \times {n!} \stackrel{\text{(definition of factorial)}}{\ge} 2^n \times 2$$

$$(n+1) \times 2^n \ge 2^n \times 2$$

Then I think I can eliminate the $2^n$ and have something like this: $n+1 \ge 2$, or $n \ge 1$.

But I think I'm wrong here some where and was hoping somebody has some advice on this. How can I prove the above assumption?

Any help would be appreciated, kind regards.

-
Looks good to me. More might be said if you wrote why you think you're wrong. –  joriki Oct 29 '11 at 16:23
I don't get why my edit was undone. How is $>=$ clearer use of $\LaTeX$ than $\ge$, and $*$ clearer than $\times$? –  Asaf Karagila Oct 29 '11 at 16:24
Please use $\backslash$ge instead of >=. –  Did Oct 29 '11 at 16:24
It’s okay now; I restored Asaf’s changes and fixed a small typo in his edit. –  Brian M. Scott Oct 29 '11 at 16:28
I did a few more changes. I hope this storm of edits dies soon. –  Srivatsan Oct 29 '11 at 16:44

In the induction step you want to show that if $k!\ge 2^k$ for some $k\ge 4$, then $(k+1)!\ge 2^{k+1}$. Since you already know that $4!\ge 2^4$, the principle of mathematical induction will then allow you to conclude that $n!\ge 2^n$ for all $n\ge 4$. You have all of the necessary pieces; you just need to put them together properly. Specifically, you can argue as follows.
Suppose that $k!\ge 2^k$, where $k\ge 4$; this is your induction hypothesis. Then \begin{align*} (k+1)! &= (k+1)k!\text{ (by the definition of factorial)}\\ &\ge (k+1)2^k\text{ (by the induction hypothesis)}\\ &> 2\cdot2^k\text{ (since }k\ge 4\text{)}\\ &= 2^{k+1}. \end{align*} This completes the induction step: it shows that if $k\ge 4$, then $$k!\ge 2^k \implies (k+1)!\ge 2^{k+1}.$$
First of all thanks for your answer. How did you go from $\ge (k+1)2^k$ to $> 2 x 2^k$? –  Floris Devriendt Oct 29 '11 at 17:01
@Floris: $k+1>2$, so $(k+1)2^k>2\cdot 2^k$. –  Brian M. Scott Oct 29 '11 at 17:04
Doesn't the 3rd step in your proof imply that $(k+1)!>2^{k+1}$ instead of $(k+1)!\geq 2^{k+1}$? –  Milosz Wielondek Apr 3 '12 at 15:15
@MiloszWielondek: But $>$ would be a stronger result than $\geq$, here so if $>$ holds then $\geq$ also holds. And he is asked to prove the statement for $\geq$. –  Mythio Apr 12 '13 at 15:40