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.

Hello I am working on this problem and was wondering if I did the proof correct.

Use induction to prove that $n! \leq n^n/2^n $ for all $n \geq 6$.

Basic Step (n=6): 6! $\leq 6^6/2^3 = 3^6$ Thus $80 \leq 81$, so the Basic Step is true.

Assume the statement above is true for n. We need to show n+1 is also true.

$(n+1)^{n+1}/2^{n+1} = (n+1)^n (n+1)/2^{n+1} \geq n^n(n+1)/2^{n+1} \geq n^n/2^{n+1} \geq n^n/2^n \geq n!$

share|improve this question
1  
You need to show, in your last inequality, that the quantity on the left is greater than or equal to $(n+1)!$, not $n!$. After all, you are proving the statement for the case $n+1$. –  Prism May 24 '13 at 9:15
2  
Don't remove the factor $n+1$. –  egreg May 24 '13 at 9:37
    
There is a significant error near the end: $n^n/2^{n+1}$ is not greater than $n^n/2^n$, it is only half the size. This $2$ is a crucial part of the question which makes it more interesting than just $n^n \ge n!$. –  Erick Wong Jun 2 '13 at 1:25
    
Select an answer dude! –  Sagnik Saha Jun 21 at 17:27

2 Answers 2

Hint: You're very close, but not quite there. Remember that $(n+1)!=(n+1)n!$.

share|improve this answer

Assuming the statement above is true for n. We need to show n+1 is also true.

$(n+1)^{n+1}/2^{n+1} = (n+1)^n (n+1)/2^{n+1} \geq n^n(n+1)/2^{n+1} \geq n^n(n+1)/2^n \geq (n^n/2^n)(n+1) \geq n!(n+1) = (n+1)!$

Thus, $(n+1)! \leq (n+1)^{n+1}/2^{n+1}$

Therefore the induction is proved for $P(n+1)$

share|improve this answer

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.