1

I'm having problem proving that $\log(n^n)=\Theta(\log(n!))$

I tried to use Stirling's formula but it seems it doesn't help me in this case.

This is what I wrote :

$$n \to \infty : \frac{\log(n!)}{\log(n^n)}=\frac{\log(\frac{\sqrt {2\pi n}}{e^n }.n^n)}{\log(n^n)}$$
Now what? nothing can be erased ... nothing can be made more simple ( Or maybe I don't know it) Any idea?

Leucippus
  • 26,329
Paolo Molina
  • 289
  • 2
    $\log(n^n)=n\cdot\log(n)$. $\log(n!)=\log(1)+\cdots+\log(n)$. Have you tried sth like this?

    It would also be nice to include you Stirling attempts in the question

     –  Feb 18 '17 at 21:18
  • @MichaelFreimann no... but how is this useful? – Paolo Molina Feb 18 '17 at 21:20
  • 1
    @PaoloMolina Given that Stirling's formula is canonically an asymptotic expression for $\log(n!)$, it's hard for us to guess what difficulty you encountered in using it. Without more details it seems extremely straightforward. But also there is a simple argument that doesn't require the precision of Stirling. – Erick Wong Feb 18 '17 at 21:23
  • Consider the second equality and just take $\sum_{i>n/2}^n \log(i)$. – Maczinga Feb 18 '17 at 21:23

1 Answers1

3

I adapted my answer for you using an older Stack Overflow post:

$$\log(n!) = \log(1) + \log(2) + \dots + \log(n-1) + \log(n)$$

Upper bound can be calculated using Sterling's approximation:

$$\log(1) + \dots + \log(n) \leq \log(n) + \dots + \log(n) \text{ or } \boxed{n\log(n)}$$

Lower bound can be determined by reasoning: your answer will be the full expression after dropping the first half:

\begin{align*} {} \log(1) + \dots + \log(\frac{n}{2}) + \dots + \log(n) \\ {} \geq \log(\frac{n}{2}) + \dots + \log(n) \\ {} \geq \log(\frac{n}{2}) + ... + \log(\frac{n}{2}) \text{ or } \boxed{\frac{n\log(n/2)}{2}} \end{align*}

Community
  • 1
David C.
  • 235