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?
Showing $\log \frac{x^x}{x!}=O(x)$
3
$\begingroup$
asymptotics
-
1You 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
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$.