How do I find the closed form sum formula of

$$\displaystyle\sum_{k=1}^{\log_2(n)}\log_2 k,$$

I was trying to do $\log_2 1 + \log_2 2 + \cdots + \log_2(\log_2 n)$ and using property of $\log$: $\log a + \log b = \log(ab)$ to get $$\log_2(1\cdot 2\cdot 3 \cdots (\log_2 n)) = \log_2((\log_2 n)!)$$ but I don't think it's right... Is there a better formula?

  • 1
    $\begingroup$ Is $n$ a power of $2$? If not, we have to figure out what the summation means; is it supposed to stop at $i = \lfloor \log_2(n)\rfloor$? That would modify your formula slightly. I think you've got it about as simple as it gets. $\endgroup$ – David K Oct 10 '18 at 4:01
  • $\begingroup$ Compare math.stackexchange.com/questions/104512/… -- but there the limit goes to $n,$ so the formula ends up that much simpler. $\endgroup$ – David K Oct 10 '18 at 4:03
  • $\begingroup$ we can assume n is a power of 2. Does that help? $\endgroup$ – randomvalue Oct 10 '18 at 4:05
  • $\begingroup$ In that case I think you already have found the answer yourself. Well done! $\endgroup$ – David K Oct 10 '18 at 4:06

Since sum indices only go over integer values, you only take the sum up to $\lfloor\log_2 n\rfloor$. That being the case, I think $\log_2(\lfloor\log_2 n\rfloor!)$ is about the best exact answer you are going to get. You could use stirling's approximation to estimate this value as $$\lfloor\log_2 n\rfloor\log_2\left(\frac{\lfloor\log_2 n\rfloor}{e}\right)+\frac{1}{2}\log_2\left(2\pi\lfloor\log_2 n\rfloor\right)$$ but I don't know how helpful that really is, and it won't be quite as accurate for $\ln(n!)$ as it is for $n!$.


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.