Prove $\log(n!) =\Omega(n\log(n))$

Question

Can someone help me prove that $\log(n!) =\Omega(n\log(n))$, that is, that there exists some positive $c$ such that, for every $n$ large enough, $\log (n!)\geqslant c\cdot n\cdot \log(n)$?

Answer 1

Suppose $\ln(n!) \ge cn\ln(n) $.

Then

$\begin{array}\\ \ln((n+1)!) &=\ln(n!)+\ln(n+1)\\ &\ge cn\ln(n)+\ln(n+1)\\ \text{and this is} &\ge c(n+1)\ln(n+1)\\ \text{if}\\ cn\ln(n)+\ln(n+1) &\ge c(n+1)\ln(n+1)\\ &= cn\ln(n+1)+c\ln(n+1)\\ &= cn(\ln(n)+\ln(1+1/n))+c\ln(n+1)\\ \text{or}\\ \ln(n+1) &\ge cn\ln(1+1/n)+c\ln(n+1)\\ \text{or}\\ (1-c)\ln(n+1) &\ge cn\ln(1+1/n)\\ \text{but}\\ \ln(1+1/n) &< 1/n\\ \text{so this is true if}\\ (1-c)\ln(n+1) &\ge c\\ \text{or}\\ \ln(n+1) &\ge \frac{c}{1-c}\\ \end{array} $

and this is true for any $c$ between $0$ and $0$ for $n \ge e^{c/(1-c)}-1 $.

To initialize, choose a $c \in (0, 1)$, get $n \ge e^{c/(1-c)}-1 $, and see if $\ln(n!) \ge cn\ln(n) $. $c = .6$ works for $n \ge 10$.

Answer 2

It's not. You might use Stirling's approximation $$ \log n! = n\log n-n+O(\log n) $$ to achieve your goal.

Answer 3

For a lower bound, note that $$(n!)^2=[1\cdot n][2\cdot (n-1)][3\cdot (n-2)]\cdots [(n-1)\cdot 2][n\cdot 1].$$ For any $k$ between $1$ and $n$, we have $k(n+1-k)\ge n$. It follows that $$(n!)^2\ge n^n,$$ and therefore $$\log(n!) \ge \frac{1}{2}n\log n.$$

Answer 4

The natural logaritm is a strictly increasing function, so for $2\leq n\in N$ we have $$\int_{n-1}^n \log x\;dx<\log n<\int_n^{n+1} \log x\;dx.$$ Therefore, for $2\leq n\in N,$we have $$n\log n -n=\int_1^n\log x \;dx<\sum_{j=2}^n\log j=\log n!$$ And for $3\leq n\in N$ we have $$\log n!=\log n+\sum _{j=2}^{n-1}\log j<\log n +\int_2^n\log x \;dx=$$ $$=(n+1)\log n-n-(2 \log 2-2).$$ Since $[n\log n-n]/n\log n\;$ and $\;[(n+1)\log n-n-(2\log 2-2)]/n\log n\;$ both converge to $1$ as $n\to \infty,$ the inequalities imply $$\lim_{n\to \infty}(n \log n)/\log n!=1.$$