I'd be really grateful if someone could help me figure out how you prove $n!\leq (n/2) ^n$ ?
Asked
Active
Viewed 94 times
6
-
Not true for $n=1$, $n=2$, $n=3$, $n=4$, $n=5$. Do you mean $(\frac{n+1}2)^n$? – Hagen von Eitzen Oct 30 '13 at 21:23
-
Nope, I rechecked the question, it's (n/2) ^n – Oct 31 '13 at 05:12
2 Answers
6
$$\sqrt[n]{n!}=\sqrt[n]{1\cdot 2\cdot 3\cdots n}\le \frac{1+2+3+\cdots+n}{n}$$ (using the arithmetic-geometric mean inequality)
Now $1+2+3+\cdots+n=\frac{n(n+1)}{2}$ (why), so the RHS becomes $\frac{n+1}{2}$. Raise each side to the power $n$ and you get $n!\le (\frac{n+1}{2})^n$, as @Hagen suggests.
vadim123
- 82,796
1
If you want a more accurate estimation, you can approximate $\log n!$ by an integral: $$ \log n! = \log 1 + \dots + \log n \leq \int_{1}^{n+1} \log x \ dx = [x \log x - x ]_{1}^{n+1} \\ = (n+1) \left(\log(\frac{n+1}{e})\right) - 1.$$ It follows that: $$ n! \leq \frac{1}{e} \left(\frac{n+1}{e}\right)^{n+1}.$$ Because $e > 2$, this implies that $n! < (n/2)^n$, if $n$ is reasonably large.
Jakub Konieczny
- 12,588