# $\frac{N\log{N}}{k\log{k}}\approx \log_{k!}{N!}$

What is the simple way to show that $$\frac{N\log{N}}{k\log{k}}\approx \log_{k!}{N!}\quad?$$

I tried to use the factorial and the log rules but..

Thanks.

-
Looks like you have $\displaystyle \log_{k^k}N^N$ and you need $N^N\approx N!$ and $k^k\approx k!$ You can find out the ranges for this approximation by inspecting this plot – kuch nahi Jul 5 '11 at 19:03
@Nir: but what? – user02138 Jul 5 '11 at 21:40
The display means that left side divided by right side approaches 1 as something approaches infinity, but what exactly is approaching infinity? Is it $N$, with $k$ held fixed? Is it $k$, with $N$ held fixed? Is it both $N$ and $k$? You can't get anywhere until you answer this question, and what's more if you say both $N$ and $k$ go to infinity, you have to say something about the relative speed with which they go to infinity. – Gerry Myerson Jul 6 '11 at 5:14

The identity isn't true. Assuming the logs are natural, take $k = e$ and $N = 2$. We have \begin{align} 0.509989... \approx \tfrac{2}{e} \log 2 = \frac{2 \log 2}{e \log e} \neq \log_{e!} 2 = \tfrac{\log 2}{\log e!} \approx 0.47281... \end{align}
Edit: I see that you replaced an equality with an approximation. In this case, it depends on the relative size of $N$ compared to $k$. To see this, just use Stirling's Approximation (on both of the factorials) \begin{align} N! \sim \sqrt{2 \pi N} \left( \frac{N}{e} \right)^{N}. \end{align} That is, \begin{align} \frac{\log N!}{\log k!} \approx \frac{N \log N + \tfrac{1}{2} (\log 2 \pi N) - N}{k \log k + \tfrac{1}{2} (\log 2 \pi k) - k} \end{align} Can you finish the argument? What else do you know about $N$ and $k$?
Noting that $\log _{k!} N! = \frac{{\log N!}}{{\log k!}}$, we want to show $$\frac{{N\log N}}{{k\log k}} \approx \frac{{\log N!}}{{\log k!}}.$$ Let us interpret this approximation as $$\frac{{\frac{{\log N!}}{{\log k!}}}}{{\frac{{N\log N}}{{k\log k}}}} \approx 1,$$ for sufficiently large $n$ and $k$. From the simple inequality* $$n\log n - n + 1 \le \log n! \le (n + 1)\log (n + 1) - n,$$ we get $$\frac{{N\log N - N + 1}}{{(k + 1)\log (k + 1) - k}} \le \frac{{\log N!}}{{\log k!}} \le \frac{{(N + 1)\log (N + 1) - N}}{{k\log k - k + 1}}.$$ Hence $$\frac{{\frac{{N\log N - N + 1}}{{(k + 1)\log (k + 1) - k}}}}{{\frac{{N\log N}}{{k\log k}}}} \le \frac{{\frac{{\log N!}}{{\log k!}}}}{{\frac{{N\log N}}{{k\log k}}}} \le \frac{{\frac{{(N + 1)\log (N + 1) - N}}{{k\log k - k + 1}}}}{{\frac{{N\log N}}{{k\log k}}}},$$ or $$\frac{{N\log N - N + 1}}{{N\log N}}\frac{{k\log k}}{{(k + 1)\log (k + 1) - k}} \le \frac{{\frac{{\log N!}}{{\log k!}}}}{{\frac{{N\log N}}{{k\log k}}}} \le \frac{{(N + 1)\log (N + 1) - N}}{{N\log N}}\frac{{k\log k}}{{k\log k - k + 1}}.$$ From this follows clearly the desired approximation.
• Obtained by bounding the sum $\sum\nolimits_{x = 1}^n {\log x} = \log n!$ with an integral from above and below; see Wikipedia for more details.