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.

I'm learning some mathematics by myself and get stuck. The problem is to show that

$n! = \omega\big((\frac{n}{3})^{n+e}\big)$, $\omega$ is the asymptotic notation.

It's from the Problem Set 7 of MIT 6.042

share|improve this question
    
Just to clarify myself on the little $\omega$ notation: $f \in \omega(g) \iff g \in o(f)$? –  user17762 Dec 27 '12 at 1:56

2 Answers 2

Hint: Use stirling approximation

share|improve this answer

\begin{align} \log(n!) & = \sum_{k=1}^n \log(k) = \int_{1^-}^{n^+} \log(t) d \lfloor t \rfloor = \log(n) n - \int_{1^-}^{n^+} \dfrac{\lfloor t \rfloor}t dt\\ & = \log(n) n - \int_{1^-}^{n^+} \dfrac{t - \{t \}}t dt = \log(n) n - n + \underbrace{\int_{1^-}^{n^+} \dfrac{\{t \}}t dt}_{> 0}\\ & > n \log n - n = \log \left(\dfrac{n^n}{e^n}\right) \end{align} Hence, we get that $n! > \left(\dfrac{n}e \right)^n$. Now prove that $$\lim_{n \to \infty} \dfrac{\left( \dfrac{n}3\right)^{n+e}}{\left(\dfrac{n}e\right)^n} = 0 $$ and then you are done.

But, $$\lim_{n \to \infty} \dfrac{\left( \dfrac{n}3\right)^{n+e}}{\left(\dfrac{n}e\right)^n} = \lim_{n \to \infty} \dfrac{(n/3)^e}{(3/e)^n} = 0$$Hence, $\left(\dfrac{n}3\right)^{n+e} \in o \left( \left(\dfrac{n}e\right)^n\right) \in o \left(\mathcal{O} \left( n!\right) \right) = o \left( n!\right)$

share|improve this answer
    
What does $d \lfloor t\rfloor $,$\{t\}$ mean ? –  Belgi Dec 27 '12 at 2:23
    
@Belgi $\lfloor t \rfloor$ denotes the greatest integer function also called the floor of $t$. $\{t\}$ is the fractional part of $t$ i.e. $\{t\} = t - \lfloor t \rfloor$. –  user17762 Dec 27 '12 at 3:46
    
Thanks for the answer, but I still don't understand the meaning of it (in the first integral) instead of $dt$ –  Belgi Dec 27 '12 at 10:58
    
@Belgi The integral I have written is nothing but a fancy way of Abel summation formula, which you may want to look at here. The integral is to be interprested as a Riemann Stieltjes integral. You may want to look at this question for more detials. math.stackexchange.com/questions/154420/… –  user17762 Dec 27 '12 at 17:54

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.