I would like to show that $\frac{\log(n!)}{n\log n}$ increases as n increases, for positive integer n only (to ignore the use of gamma function). Note here $\log n = \ln(n)$, so using base e. I would like to be able to show this so I can then apply the Monotone Convergence Theorem to show that $(\log(n!)\sim(n\log n)$. My first idea was to try and show that the second derivative is always positive, but due to $\log(n!)$ not being continuous (without having to use gamma function which I feel is OTT for this question) this, of course, would not work. Does anyone have any ideas about how to prove that this sequence is increasing rigorously?


Hint: You can use Stirling approximation for $n!$: $$n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$ Or: $$n! = \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \left(1+O\left(\frac{1}{n}\right)\right)$$ To know more about how to use this approximation you can see this link.

  • $\begingroup$ This is not rigorous if one simply uses the approximation. $\endgroup$ – Carl Schildkraut Feb 28 '18 at 21:58
  • $\begingroup$ @CarlSchildkraut As he wants to approximate $\log(n!) \sim n \log n$, it can be helpful. $\endgroup$ – OmG Feb 28 '18 at 22:03
  • 1
    $\begingroup$ It can be helpful, but the approximation (without effective error terms) cannot act as a proof all on its own. The function $f(n)$ which equals $n!$ at $n\neq 10$ and $10^{10^{10}}$ at $n=10$ is asymptotic to $n!$, yet if $n!$ is replaced by $f(n)$ in the question, the relation is false as the term at $n=11$ is less than that at $n=10$. $\endgroup$ – Carl Schildkraut Feb 28 '18 at 22:09
  • $\begingroup$ @CarlSchildkraut you're right. More details about this approximation and bounds are provided in the inserted link. $\endgroup$ – OmG Feb 28 '18 at 22:13
  • $\begingroup$ @OmG Funnily enough I'm trying to prove this en route to learning about Stirling's formula, and so I am looking for a simpler proof without use of Stirling's approximation, which I am trying to derive via this! $\endgroup$ – Daniele1234 Feb 28 '18 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.