1

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

Gerry Myerson
  • 179,216
Username Unknown
  • 4,633
  • 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 09:15
  • 2
    Don't remove the factor $n+1$. – egreg May 24 '13 at 09: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 02 '13 at 01:25

2 Answers2

1

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

Cameron Buie
  • 102,994
0

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

thesagniksaha
  • 355