TAOCP 1.2.3 Exercise 16

Let S=\sum_{j=0}^n jx^j.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.3: Sums and Products

Exercise 16. [M22] Prove that

$$\sum_{j=0}^n jx^j = \frac{nx^{n+2} - (n+1)x^{n+1} + x}{(x-1)^2},$$

if $x \ne 1$, without using mathematical induction.

Verified: yes
Solve time: 31s

Solution

Let

$$ S=\sum_{j=0}^n jx^j. $$

Since the term corresponding to $j=0$ is zero,

$$ S=\sum_{j=1}^n jx^j. $$

Multiply by $x$:

$$ xS=\sum_{j=1}^n jx^{j+1}. $$

By rule (b), replacing $j$ by $j-1$,

$$ xS=\sum_{j=2}^{n+1} (j-1)x^j. $$

Now subtract:

$$ xS-S=\sum_{j=2}^{n+1} (j-1)x^j-\sum_{j=1}^n jx^j. $$

Separate the boundary terms and combine the overlapping sums:

$$ \begin{aligned} xS-S &=nx^{n+1}+\sum_{j=2}^n\bigl((j-1)-j\bigr)x^j-x \ &=nx^{n+1}-\sum_{j=2}^n x^j-x \ &=nx^{n+1}-\sum_{j=1}^n x^j. \end{aligned} $$

Hence

$$ (x-1)S=nx^{n+1}-\sum_{j=1}^n x^j. $$

By Eq. (14),

$$ \sum_{j=1}^n x^j =\sum_{j=0}^n x^j-1 =\frac{1-x^{n+1}}{1-x}-1. $$

Since

$$ -1=\frac{x-1}{1-x}, $$

we obtain

$$ \sum_{j=1}^n x^j =\frac{1-x^{n+1}+x-1}{1-x} =\frac{x-x^{n+1}}{1-x}. $$

Therefore

$$ (x-1)S =nx^{n+1}-\frac{x-x^{n+1}}{1-x}. $$

Because

$$ \frac{1}{1-x}=-\frac{1}{x-1}, $$

this becomes

$$ (x-1)S =nx^{n+1}+\frac{x-x^{n+1}}{x-1}. $$

Multiply by $(x-1)$:

$$ (x-1)^2S =nx^{n+1}(x-1)+x-x^{n+1}. $$

Expand:

$$ \begin{aligned} (x-1)^2S &=nx^{n+2}-nx^{n+1}+x-x^{n+1} \ &=nx^{n+2}-(n+1)x^{n+1}+x. \end{aligned} $$

Hence

$$ \boxed{ \sum_{j=0}^n jx^j = \frac{nx^{n+2}-(n+1)x^{n+1}+x}{(x-1)^2} } $$

for $x\ne1$. ∎