Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Looks good to me. More might be said if you wrote why you think you're wrong. –  joriki Oct 29 '11 at 16:23
2  
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
2  
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
1  
I did a few more changes. I hope this storm of edits dies soon. –  Srivatsan Oct 29 '11 at 16:44

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
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
    
oh okay I get it, thanks! –  Floris Devriendt Oct 29 '11 at 17:42
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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