# How to show $n! = \omega\big((\frac{n}{3})^{n+e}\big)$?

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

• 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

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

• 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