2
$\begingroup$

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

  • 0
    Just to clarify myself on the little $\omega$ notation: $f \in \omega(g) \iff g \in o(f)$?2012-12-27

2 Answers 2

1

Hint: Use stirling approximation

0

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

  • 0
    @Belgi The integral I have written is nothing but a fancy way of Abel summation formula, which you may want to look at [here](http://en.wikipedia.org/wiki/Abel's_summation_formula). The integral is to be interprested as a Riemann Stieltjes integral. You may want to look at this question for more detials. http://math.stackexchange.com/questions/154420/eulers-summation-by-parts-formula2012-12-27