Can somebody look over my proof? (Asymptotic notation and algorithms)

[scorpion4377]

Hey. I'm self studying my way through an algorithms book, and one of the questions at the end of a section is to prove that log(n!) \in \Theta (n log(n)). I wrote up what I believe is a valid proof. However, I don't have much experience writing formal proofs (and even less experience with having my proofs corrected by professionals), so it could very well be invalid/lingered with errors. Can somebody take a quick look at it and comment on any mistakes that may exist? Can you comment on my style? Any advice would be appreciated.

Here is my write-up. I apologize for not using the built-in equation editor.

http://i.imgur.com/iyAto.png

 

[Millennial]

I think Stirling's formula is unnecessary here. An asymptotic expression for \log(n!) can be obtained as follows:
\log(n!)=\sum_{k=1}^{n}\log(k) \sim \int_{1}^{n}\log(x)dx
The integral on the right side can be evaluated using integration by parts:
\int \log(x)dx = x\log(x) - \int dx = x\log(x)-x+C
and this yields
\log(n!) \sim n\log(n)-n \sim n\log(n)
Can you take it from there?

 

[scorpion4377]

That wouldn't be rigorous, would it? In my proof, I kept the error terms and treated them rigorously.

EDIT: The point of the problem is to proof the asymptotic behavior of the function, so it would be self defeating to use its asymptotic form. Please correct me if I am wrong, though.

 

[AlephZero]

You can get the error bounds from post #2.
$$\log(n!) = \sum_{k=2}^n \log k$$
I changed the lower limit since $\log 1 = 0$.

Because $\log$ is a monotonic function you can bracket the sum by two integrals
$$\int_2^n \log (x-1)\,dx < \sum_{k=2}^n \log k < \int_2^n \log x\,dx$$

Draw a picture of the integrals and the sum as a set of rectangles, if you can't see where that came from.

 

[scorpion4377]

I see! That definitely looks like a valid proof, too. The book that I'm using mentioned bounding functions using integrals, but for some reason told me to use Sterling's formula to prove the theorem.