Comp Sci 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.