The Art of Computer Programming - Section 1.2.3, First Set, Exercise 16

Problem:

Solution:

The trick is to differentiate the geometric series on both side


$\begin{eqnarray*} \sum\limits_{j = 0}^{n}x^j &=& \frac{x^{n+1} - 1}{x - 1} \\ \frac{d}{dx}(\sum\limits_{j = 0}^{n}x^j) &=& \frac{d}{dx}(\frac{x^{n+1} - 1}{x - 1}) \\ \sum\limits_{j = 0}^{n}\frac{d}{dx}(x^j) &=& \frac{d}{dx}(\frac{x^{n+1} - 1}{x - 1}) \\ \sum\limits_{j = 0}^{n}jx^{j - 1} &=& \frac{d}{dx}(\frac{x^{n+1} - 1}{x - 1}) \\ \sum\limits_{j = 0}^{n}jx^j &=& x\frac{d}{dx}(\frac{x^{n+1} - 1}{x - 1}) \\ &=& x\frac{(x-1)(x^{n+1} - 1)' - (x^{n+1} - 1)(x-1)'}{(x - 1)^2} \\ &=& x\frac{(x-1)(n+1)x^n - (x^{n+1} - 1)}{(x - 1)^2} \\ &=& x\frac{(n+1)x^{n+1} - (n+1)x^n - x^{n+1} + 1}{(x - 1)^2} \\ &=& x\frac{nx^{n+1} - (n+1)x^n + 1}{(x - 1)^2} \\ &=& \frac{nx^{n+2} - (n+1)x^{n+1} + x}{(x - 1)^2} \\ \end{eqnarray*}$