Is there a closed form for...

Question

I was working on an analysis question, and was wondering if there's a closed form for $\sum_{i=0}^{log(n)}(1/2^i)log(i)$? Unless I have made a mistake, I am trying to show that $n\sum_{i=0}^{log(n)}(1/2^i)log(i) \in \Theta(n)$.

Thanks!

Answer 1

You are interested in the sum $$S(n) = \sum_{i=1}^n \dfrac{\log(i)}{2^i}$$ Note that we have $\log(i) < i$ and hence we have $$S(n) < \sum_{i=2}^n \dfrac{i}{2^i} = \dfrac32 - \dfrac{n+2}{2^n} < \dfrac32$$