Proving Both Upper and Lower Bounds for Stirling's Approximation

[rxh140630]

Homework Statement

prove lg(n!) = thetha(nlgn) where lg n is log with base = 2. Use Sterling's approximation as a hint

Relevant Equations

Sterling's approximation: $n! = \sqrt(2*pi*n)(\frac{n}{e})^n(1+ \theta{1/n})$

Sterling's approximation: $n! = \sqrt{2*pi*n}(\frac{n}{e})^n(1+ \theta(1/n))$

So I need to prove

$c_1nlgn ≤lg(\sqrt{2*pi*n}) + lg((\frac{n}{e})^n) + lg(1+ \theta(1/n))) ≤ c_2nlgn$

My question is:

assume I've proven $lg(\sqrt{2*pi*n})$ as $\theta(lgn)$

Do I need to now prove that $c_1nlgn ≤ lgn ≤ c_2nlgn$ ??

What if we assume I found that $lg(\sqrt{2*pi*n})$ as $\theta(\sqrt{n})$

Do I need to now prove that $c_1nlgn ≤ \sqrt{n} ≤ c_2nlgn$ ??

Assuming the other terms in the sum $g(\sqrt{2*pi*n}) + lg((\frac{n}{e})^n) + lg(1+ \theta(1/n)))$ are proven to be $\theta(nlgn)$

 

[fresh_42]

The upper and lower bounds of Stirling's formula are so good, that I would use both of them just to be on the safe side.
$$
1< e^{1/(12n+1)} < \dfrac{n!}{\sqrt{2\pi n}\cdot\left(\dfrac{n}{e}\right)^n} < e^{(1/12n)}< 1+\dfrac{1}{11n}
$$

The formal definition of the theta notation is:
$$
f(x)=\theta(g(x)) \Longleftrightarrow 0<\operatorname{lim\,inf}_{x\to a}\left|\dfrac{f(x)}{g(x)}\right|\leq \operatorname{lim\,sup}_{x\to a}\left|\dfrac{f(x)}{g(x)}\right|<\infty
$$
so, yes, you have to manage both ends.