How to prove that $\log_2(n!) = \Theta(n\log_2[n])$?

Question

My first thought was to use $$\lim_{n\rightarrow\infty}\frac{n!}{n^n} = 0$$so I thought it should be $$\log_2n!=O(n\log_2n=\log_2n^n)$$ but I was told that $$\log_2n!=\Omega(n\log_2n)$$ is also true. So per definition I have to find $\alpha>0$ s.t. $$\exists n_0\in\Bbb N : \forall n\geq n_0 (n \in \Bbb N) \\\log_2n!\geq \alpha\cdot\log_2n^n$$ What is the idea to deal with this? Thanks in advance!

Cheers

Answer 1

The inequalities $$ (n/2)^{(n/2)} \le n! \le n^n $$ are easy. Take logs.

Answer 2

$\log n!=\sum_{k=1}^n\log k$, which lies between $\int_0^n\log x\,\mathrm dx$ and $\int_1^{n+1}\log x\,\mathrm dx$ because $\log$ is monotonic.

(P.S. This is part of the idea behind Stirling's approximation.)

Answer 3

By considering only the largest $n/2$ terms of $n!$, we have $n! \geq \left(\dfrac{n}{2}\right)^{n/2}$, so

$$\log_2 n! \geq \log_2 \left(\left(\frac{n}{2}\right)^{n/2}\right) = \frac{1}{2} \left(n \log_2 n\right) - \frac{1}{2} (n \log_2 2) = \frac{1}{2} \left(n \log_2 n\right) - \frac{1}{2} n.$$

For large $n$, the term $n$ is negligible compared to the term $n \log_2 n$. So taking $\alpha$ slightly less than $1/2$ and $n_0$ sufficiently large should work.

Answer 4

Try using that

$$\lim_n \frac{\sqrt[n]{n!}}{n} =\frac{1}{e}$$

Then

$$\sqrt[n]{n!}\geq (\frac{1}{e}-\epsilon)n \,.$$

or

$$\log_2(n!) \geq n \log_2 (\frac{1}{e}-\epsilon)+\log_2(n^n) \,.$$

Now, all you have to do is find some $\beta<1$ so that

$$ \log_2 (\frac{1}{e}-\epsilon) \geq \beta \log_2(\frac{1}{n})$$

PS For the first limit, if you didn't see it before, just take the $\ln$ and apply Stolz-Cezaro.

Answer 5

I came across the same limit some months ago, my idea was this:

$$\lim _{n\rightarrow+\infty } \dfrac{\ln(n!)}{\ln(n^n)}=\lim _{n\rightarrow +\infty} \dfrac {n\ln (n)+\sum _{k=1}^{n}\ln (1-\frac {k}{n}) }{n\ln(n)}=1+\ell $$

assuming the last part converges. Then (multiplying by $\frac{n}{n}$):

$$\ell =\lim _{n\rightarrow+\infty }\dfrac{\sum _{k=1}^{n}\ln (1-\frac{k}{n})^{n}}{n^2\ln n}$$

Here comes the part that I don't know how to formalize better and it would be great if someone is able to fix this:

$$\ell=\lim _{n\rightarrow+\infty}\dfrac{\sum_{k=1}^{n}\ln (1-\frac{k}{n})^n}{n^2\ln n}\sim \dfrac {\sum_{k=1}^{\infty}k}{\lim_nn^2\ln n}\sim \lim _{n\rightarrow+\infty }\dfrac{O(n^2)}{n^2\ln n}=0$$