Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Stirling's formula link can help. –  Idan Jan 27 '13 at 16:49
    
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. –  Louis Jan 27 '13 at 16:57
    
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. –  Rahul Jan 27 '13 at 17:14

5 Answers 5

up vote 3 down vote accepted

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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