0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Stirling's formula link can help. $\endgroup$
    – Idan
    Jan 27, 2013 at 16:49
  • $\begingroup$ Maybe somebody should close this question, since it, and my answer below, are basically isomorphic to the one [math.stackexchange.com/posts/93422/revisions here] from a while ago. $\endgroup$
    – Louis
    Jan 27, 2013 at 16:57
  • $\begingroup$ Direct link to the question in @Louis's comment: Proof that $\sum\limits_{i=1}^k\log(i)$ belongs to $O(k)$. Since the question itself is incorrect (though the answers aren't), I'm a little reluctant to vote to close. $\endgroup$
    – user856
    Jan 27, 2013 at 17:14
  • $\begingroup$ I just found by pairing the double products that $n!\le\bigl((\frac{n+1}{2})^2-(\frac{n}{4})^2\bigr)^{n/2}$, for $n\ge 2$, and upper bound is much closer to $n!$ than $n^n$ is, but not proved. $\endgroup$
    – MathArt
    Feb 4 at 9:21

5 Answers 5

5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.