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

Question

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 05 '11 at 08:11

score 6 · Accepted Answer · answered Dec 05 '11 at 07:54

6

Stirling's approximation

answered Dec 05 '11 at 07:54

N. S.

132,525

I didn't think of that, thanks! – Carolus Dec 05 '11 at 08:43

score 2 · Answer 2 · answered Dec 05 '11 at 10:09

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$.

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

2 Answers2