3
$\begingroup$

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?

  • 1
    You are missing an expansion of $\log{x!}$ that allows comparison with $x \log{x}$. It is $x\log x-x+O(\log{x})$2011-12-05

2 Answers 2

6

Stirling's approximation

  • 0
    I didn't think of that, thanks!2011-12-05
2

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