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

  • $\begingroup$ Just to clarify myself on the little $\omega$ notation: $f \in \omega(g) \iff g \in o(f)$? $\endgroup$ – user17762 Dec 27 '12 at 1:56

Hint: Use stirling approximation


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

  • $\begingroup$ What does $d \lfloor t\rfloor $,$\{t\}$ mean ? $\endgroup$ – Belgi Dec 27 '12 at 2:23
  • $\begingroup$ @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$. $\endgroup$ – user17762 Dec 27 '12 at 3:46
  • $\begingroup$ Thanks for the answer, but I still don't understand the meaning of it (in the first integral) instead of $dt$ $\endgroup$ – Belgi Dec 27 '12 at 10:58
  • $\begingroup$ @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/… $\endgroup$ – user17762 Dec 27 '12 at 17:54

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.