# Showing $\log \frac{x^x}{x!}=O(x)$

I need to finish off a problem by showing that $\log (x^x/x!)=O(x)$. My first thought (after looking at a plot) was, "hah! this is easy...", but it appears I am unable to prove this. What I've got so far (and this might very well be in the wrong direction) is: $$\log \frac{x^x}{x!}=\log x^x+\log 1-\log x!=x \log x- \log x!.$$ What am I missing?

-
You are missing an expansion of $\log{x!}$ that allows comparison with $x \log{x}$. It is $x\log x-x+O(\log{x})$ –  Henry Dec 5 '11 at 8:11

-
I didn't think of that, thanks! –  Carolus Dec 5 '11 at 8:43

Here's a proof not using Stirling's formula (but equivalent to a very rudimentary version of it):

One the one hand, we have

$$\int_1^x \log t dt = x(\log x-1)+1.$$

Also, $\log t$ is increasing and therefore, if $x=n$ is an integer,

$$\int_1^n \log t dt = \sum_{j=1}^{n-1}\int_j^{j+1}\log t dt < \sum_{j=1}^{n-1} \log(j+1) = \log n!.$$

Thus $n \log n - \log n! < n-1$.

-