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
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
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
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer


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.