0
$\begingroup$

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?

$\endgroup$
4
  • 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, 2018 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, 2018 at 4:03
  • $\begingroup$ we can assume n is a power of 2. Does that help? $\endgroup$ Oct 10, 2018 at 4:05
  • $\begingroup$ In that case I think you already have found the answer yourself. Well done! $\endgroup$
    – David K
    Oct 10, 2018 at 4:06

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .