TAOCP 1.2.3 Exercise 15
Let S_n=\sum_{j=1}^{n} j2^j.
Section 1.2.3: Sums and Products
Exercise 15. ▶ [M22] Compute the sum $1 \times 2 + 2 \times 2^2 + 3 \times 2^3 + \cdots + n \times 2^n$ for small values of $n$. Do you see the pattern developing in these numbers? If not, discover it by manipulations similar to those leading up to Eq. (14).
Verified: yes
Solve time: 1m15s
Solution
Let
$$ S_n=\sum_{j=1}^{n} j2^j. $$
For small values of $n$,
$$ S_1=2, $$
$$ S_2=2+8=10, $$
$$ S_3=2+8+24=34, $$
$$ S_4=2+8+24+64=98. $$
These values satisfy
$$ 2=2+(1-1)2^2, $$
$$ 10=2+(2-1)2^3, $$
$$ 34=2+(3-1)2^4, $$
$$ 98=2+(4-1)2^5. $$
This suggests the formula
$$ S_n=2+(n-1)2^{n+1}. $$
To derive it by manipulations similar to those leading to Eq. (14), write
$$ S_n=\sum_{1\le j\le n} j2^j. $$
Then
$$ 2S_n=\sum_{1\le j\le n} j2^{j+1} =\sum_{2\le j\le n+1} (j-1)2^j, $$
by rule (b), using the change of variable illustrated in Eq. (6).
Separate the first and last terms by rule (d):
$$ 2S_n = \sum_{2\le j\le n}(j-1)2^j +n2^{n+1}. $$
Subtracting $S_n$ gives
$$ 2S_n-S_n = \sum_{2\le j\le n}(j-1)2^j +n2^{n+1} - \sum_{1\le j\le n}j2^j. $$
Combining the sums term-by-term,
$$ S_n = n2^{n+1} -\sum_{2\le j\le n}2^j -2. $$
The remaining sum is geometric. By Eq. (14), with $a=2$, $x=2$, and $n-1$ in place of $n$,
$$ \sum_{0\le k\le n-1}2^{k+1} = 2(2^n-1). $$
Hence
$$ \sum_{2\le j\le n}2^j = \sum_{1\le j\le n}2^j-2 = \bigl(2(2^n-1)\bigr)-2 = 2^{n+1}-4. $$
Substituting,
$$ S_n = n2^{n+1} -(2^{n+1}-4) -2 = (n-1)2^{n+1}+2. $$
Therefore
$$ \sum_{j=1}^{n} j2^j = 2+(n-1)2^{n+1}. $$
Thus the value of the sum is
$$ \boxed{\sum_{j=1}^{n} j2^j = 2+(n-1)2^{,n+1}}. $$