# closed form formula question

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?

• 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. – David K Oct 10 '18 at 4:01
• Compare math.stackexchange.com/questions/104512/… -- but there the limit goes to $n,$ so the formula ends up that much simpler. – David K Oct 10 '18 at 4:03
• we can assume n is a power of 2. Does that help? – randomvalue Oct 10 '18 at 4:05
• In that case I think you already have found the answer yourself. Well done! – David K Oct 10 '18 at 4:06

## 1 Answer

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!$$.