How to prove that $\;n\log(n) = O(\log(n!))$ How can I start from $\;n\log(n)\;$ and show that $\;n\log n\leqslant c\cdot\log(n!)\;$ for $\;c>0\;.$
I understand how to show that $\;n\log(n!)>\dfrac n2\cdot\log\left(\dfrac n2\right)\;.$
How can I continue from there?
 A: You might want to start from $\log n!=\log1+\log2+\cdots+\log n$,
Using Gauss' schoolboy trick for summing $1+2+\cdots+n$ we can say
$$ 2\log n!=\log(1\cdot n)+\log(2\cdot (n-1))+\cdots+\log(n\cdot1). $$
Can you continue from here?
A: $\ln(n!)=\sum_{k=1}^{n}\ln(k)\leq n\ln n$. On the other hand,
\begin{eqnarray*}
\sum_{k=2}^{n}\ln k & \geq & \sum_{k=2}^{n}\int_{k-1}^{k}\ln x\,dx\\
 & = & \int_{1}^{n}\ln x\,dx\\
 & = & \left[x\ln x\right]_{1}^{n}-\int_{1}^{n}dx\\
 & = & n\ln n-(n-1).
\end{eqnarray*}
For $n\geq e^{4}$, $n\ln n\geq n\cdot\ln e^{4}=4n$. Hence, $n\ln n-(n-1)\geq\frac{1}{2}n\ln n+\frac{1}{2}\cdot4n-(n-1)\geq\frac{1}{2}n\ln n$.
We conclude that, for $n\geq e^{4},$
$$
\frac{1}{2}n\ln n\leq\ln(n!)\leq n\ln n.
$$
It follows that $n\ln n\sim O(\ln(n!))$.
Remark: Actually, we can do more. Clearly, $\frac{\ln(n!)}{n\ln n}\leq1$
and $\frac{\ln(n!)}{n\ln n}\geq\frac{n\ln n-(n-1)}{n\ln n}=1-\frac{n-1}{n}\cdot\frac{1}{\ln n}\rightarrow1$
as $n\rightarrow\infty$. By sandwich rule, we have that $\lim_{n\rightarrow\infty}\frac{\ln(n!)}{n\ln n}=1$.
A: $\displaystyle\;\log\big(n!\big)=\sum\limits_{k=1}^n\log k\leqslant\sum\limits_{k=1}^n\log n=n\log n\;.$
Moreover,
$\displaystyle n\log n=\sum\limits_{k=1}^n\log n\leqslant\sum\limits_{k=1}^n\log\big[(n-k)(k-1)+n\big]=$
$\displaystyle=\sum\limits_{k=1}^n\log\big(kn-k^2+k\big)=\sum\limits_{k=1}^n\log\big[k(n-k+1)\big]=$
$\displaystyle=\sum\limits_{k=1}^n\log k+\sum\limits_{k=1}^n\log\big(n-k+1\big)=$
$\displaystyle=\sum\limits_{k=1}^n\log k+\sum\limits_{h=1}^n\log h=2\sum\limits_{k=1}^n\log k=$
$\displaystyle=2\log\big(n!\big)\;.$
Hence, it results that
$\log\big(n!\big)\leqslant n\log n\leqslant 2\log\big(n!\big)\;.$
