2

I'm trying to solve a recurrence relation and came across this term $\sum_{i=0}^n i9^i$? I thought this was a geometric series, but I guess it's not. Is it possible to solve this?

dev_nut
  • 161
  • 3
  • 11

2 Answers2

2

HINT: The geometric series you refer to has closed form:

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

Can you figure out through differentiation how to derive the solution for $\sum_{k=0}^{n}kx^k$? Then plugging in $9$ will give you the particular solution you are looking for.

EDIT

The derivative of the RHS above is $\sum_{k=0}^{n}kx^{k-1}$. After multiplying by $x$ we get the general form of your series in question.

Next we differentiate the LHS and get:

$$\frac{-(n+1)x^n(1-x)-(-1)(1-x^{n+1})}{(1-x)^2}$$

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

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

After multiplying by $x$ we have finally:

$$\sum_{k=0}^{n}kx^k = \frac{x-x^{n+1}(n+1)+nx^{n+2}}{(1-x)^2}$$

Patrick
  • 2,106
  • I don't follow your hint that well. My knowledge of series and series summation is not that great. – dev_nut Sep 26 '13 at 01:31
  • As usual, Andre has the best answer. I edited my post to follow through with my hint in case you are interested in the method. – Patrick Sep 26 '13 at 01:48
  • Thanks, this certainly makes more sense now, and will be quite useful. – dev_nut Sep 26 '13 at 03:55
1

Let $S$ be our sum. Then $$S=9+2\cdot 9^2+3\cdot 9^3+\cdots+n\cdot 9^n.$$ Multiply through by $9$. We get $$9S=9^2+2\cdot 9^3+3\cdot 9^4+\cdots+n\cdot 9^{n+1}.$$ Subtract. We get $$8S=-(9+9^2+9^3+\cdots +9^n)+n\cdot 9^{n+1}.$$ You probably know how to find a closed form for the geometric series $9+9^2+9^3+\cdots+9^n$. Now simplify, and solve for $S$.

André Nicolas
  • 507,029
  • Thanks that works. Is there a general theorem or rule that can be applied to a series like this? – dev_nut Sep 26 '13 at 01:31
  • There is nothing special about $9$, the same idea works for $r$ anything but $1$. For more general problems, like $\sum_1^n k^29^k$, variants of the method in Patrick's answer can be handy, though the method in the above answer also generalizes. – André Nicolas Sep 26 '13 at 01:35