Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment

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.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.