online advertising
Showing posts with label The Art of Computer Programming. Show all posts
Showing posts with label The Art of Computer Programming. Show all posts

Saturday, April 2, 2016

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*} $