$Which \;of\; these \;sums\; is\; asymptotically\; closer \;to\; the\; value\; log_mn!?$

$ \sum_{k=1}^n\lfloor\;log_m k\;\rfloor$


$\sum_{k=1}^n\lceil\;log_m k\;\rceil$

Has anything to do with Stirling's formula?

  • $\begingroup$ I looked Stirling's formula but cannot understand the connection,if there is one. $\endgroup$ – Mary L. Jan 6 '17 at 21:42
  • $\begingroup$ Have you tried any numerical experiments? The easiest could be using $m=10$? $\endgroup$ – Fabio Somenzi Jan 6 '17 at 21:50
  • $\begingroup$ Perhaps I'm missing something, but it would seem to me that the ceiling version would be much greater than the log in question, since it would include that log (rounded up), plus the log of all smaller numbers! So I would expect the floor version to be closer. $\endgroup$ – Wildcard Jan 6 '17 at 22:02
  • $\begingroup$ Why have you enclosed all your text in dollar signs? $\endgroup$ – Arthur Jan 6 '17 at 22:27

Assume that $m$ is greater than $n!$, and $n\geq 2$. Thus, $\log_m{n!}<1$, but for $1< k\leq n$ $$\lfloor\log_m k\rfloor=0\\\lceil\log_m k\rceil=1$$ which results in $$\sum_{k=1}^n \lfloor\log_m k\rfloor=0\\\sum_{k=1}^n \lceil\log_m k\rceil=n-1\\$$ Obviously for such cases the floor function provides better approximation, though nothing but zero. However, there may be cases with the opposite result.

  • $\begingroup$ I don't see where this answers the "asymptotically" part. As $n$ approaches infinity, of course $m \not\gt n!$. $\endgroup$ – Wildcard Jan 6 '17 at 22:19
  • 1
    $\begingroup$ You're right. I totally skipped the "asymptotically" part. $\endgroup$ – Babak Jan 7 '17 at 7:22

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.