How to compute the formula $\sum \limits_{r=1}^d r \cdot 2^r$?
Given $$1\cdot 2^1 + 2\cdot 2^2 + 3\cdot 2^3 + 4\cdot 2^4 + \cdots + d \cdot 2^d = \sum_{r=1}^d r \cdot 2^r,$$ how can we infer to the following solution? $$2 (d-1) \cdot 2^d + 2. $$
Thank you
There are at least five ways:
- Use plain induction.
- Differentiate the identity for the sum of a geometric series.
- Find some combinatorial interpretation for both sides and provide a bijection.
- Write as a sum of geometric series, sum each individual series, and sum the resulting geometric series.
- Divide both sides by $2^d$ and slightly modify the sum so that it has some probabilistic interpretation. Use known properties of the relevant random variable.
As noted above, observe that \begin{eqnarray} \sum_{r = 1}^{d} x^{r} = \frac{x(x^{d} - 1)}{x - 1}. \end{eqnarray} Differentiating both sides and multiplying by $x$, we find \begin{eqnarray} \sum_{r = 1}^{d} r x^{r} = \frac{dx^{d + 2} - x^{d+1}(d+1) + x}{(x - 1)^{2}}. \end{eqnarray} Substituting $x = 2$, \begin{eqnarray} \sum_{r = 1}^{d} r 2^{r} = d2^{d + 2} - (d+1) 2^{d+1} + 2 = (d - 1) 2^{d+1} + 2. \end{eqnarray}
Perhaps a sixth way...
$$\displaystyle S = \sum_{r=1}^{d} r\cdot 2^r$$
$$\displaystyle 2S = \sum_{r=1}^{d} r\cdot 2^{r+1} = \sum_{r=2}^{d+1} (r-1)2^{r}$$
$$\displaystyle 2S -S = d\cdot 2^{d+1} - \sum_{r=1}^{d} 2^r = d\cdot 2^{d+1} - 2^{d+1} +2 = (d-1)2^{d+1} + 2$$