What is the generalized formula for the sum of the series represented by $\sum_{i=0}^ {\log_2 (n)-1} (2^i\cdot i)$?

Question

I am trying to find out the generalized formula for the sum of this series, which looks like: $$2^0 \cdot 0 + 2^1 \cdot 1 + 2^2 \cdot 2 + \dots + 2^{\log_2(n)-1} \cdot (\log_2(n)-1)$$ which I have represented as $$\sum_{i=0}^{\log_2(n)-1} (2^i\cdot i)$$ where $n=2^m, m>0$.

Could you somebody help me out with a solution for this?

Answer 1

The sum is essentially $\sum_{k=0}^{m-1} k z^k$ evaluated at $z = 2$. Notice

$$\sum_{k=0}^{m-1} k z^k = \sum_{k=0}^{m-1} \left(z\frac{d}{dz}\right) z^k = \left(z\frac{d}{dz}\right)\sum_{k=0}^{m-1} z^k = \left(z\frac{d}{dz}\right)\frac{1-z^m}{1-z} = \frac{-mz^m}{1-z} + \frac{z(1-z^m)}{(1-z)^2} $$ The sum at hand equals to $$\frac{-m2^m}{1-2} + \frac{2(1-2^m)}{(1-2)^2} = m 2^m - 2(2^m - 1) = (m-2)2^m + 2$$

Answer 2

First, consider the series $ S = 2^0 \cdot 0 + 2^1 \cdot 1 + 2^2 \cdot 2 + . . . + 2^{m-1} \cdot (m-1)$

Then, $ 2 \cdot S = 2^1 \cdot 0 + 2^2 \cdot 1 + 2^3 \cdot 2 + . . . + 2^{m-1} \cdot (m-2) + 2^m \cdot (m-1) $

$ S = 2\cdot S - S = (m-1) \cdot 2^{m} - \sum_{k=1}^{m-1} 2^k.$

But $\sum_{k=1}^{m-1} 2^k $ is a geometric progression, which evaluates to $2^m - 2.$

$S = (m-1) \cdot 2^m - (2^m - 2)$

$S = 2^m \cdot (m-2) +2 $

Since $n = 2^m$, $ S = n \cdot (log_2{n} - 2) + 2$.