need help in finding closed form for $\sum_{i=0}^{\log(n/2)} \frac{n}{2^i}\log\frac{n}{2^i}$

Question

I need help in finding a closed form for $$\sum_{i=0}^{\log(n/2)} \frac{n}{2^i}\log\frac{n}{2^i}$$ I am not sure even where to start. I know there is a closed form for $$f(x) = \sum_{i=0}^\infty \frac{x}{2^i} = 2x,$$ but this does not seem to help really... How would I find a closed form?

Thanks

Answer 1

Hint: $$ \frac{n}{2^i}\log_2 \frac{n}{2^i} = n\log_2 n\cdot\frac{1}{2^i} - n\cdot \frac{i}{2^i} $$ so, knowing $\sum_{i=0}^m \frac{1}{2^i}$ and $\sum_{i=0}^m \frac{i}{2^i}$, you can conclude. (using $m=\log_2\frac{n}{2}$)

Hint #2:

The first sum is easy and well-known, as the partial sum of a geometric series. The second is not much harder: observe that you want $f(1/2)$, where $f(x) = \sum_{i=0}^m i x^i = x\sum_{i=1}^m i x^{i-1} = x g^\prime(x)$, where $g(x) = \sum_{i=0}^m x^i$ is again the partial sum of a geometric series.