# Conversion of a sum to a closed form with an index and then losing the index

I'm reading the solution of a recurrence relation exercise. I think I understand the solution, except for the two following steps:

$$\cdots = \displaystyle{\underbrace{\left( -1\right) ^{n}\sum _{k=0}^{n}\left( -2\right) ^{k}}_{(1)} =\underbrace{\left( -1\right) ^{n}\dfrac {\left( -2\right) ^{k}} {-3}\bigg|_{0}^{n+1}}_{(2)}} = \underbrace{\frac {(-1)^{n+1}}{3}((-2)^{n+1}-1)}_{(3)}= \cdots$$

How do you go from $(1)$ to $(2)$ - which, as we see, converts the summation in $(1)$ to a closed form in $(2)$, but that still uses the $k$ index - and then from $(2)$ to $(3)$ - thereby losing the index $k$?

-

Going from (1) to (2), they are using $1+r+r^2+\cdots+r^n=\frac{1-r^{n+1}}{1-r}$ with $r=-2$, and then going from (2) to (3) they are substituting $n+1$ and $0$ in for $k$ and subtracting, and using that $\frac{(-1)^{n}}{-1}=(-1)^{n+1}$.

-

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

-
$$f(x) |_b^a = f(a) -f(b)$$ –  what'sup Sep 6 '13 at 22:37

For getting to step (2), let $S=\sum\limits_{k=0}^n(-2)^k$. Observe multiplying throughout $-2$ yields $-2S=\sum\limits_{k=1}^{n+1}(-2)^k$. The difference between the two is then just:\begin{align*}-2S-S&=\sum_{k=1}^{n+1}(-2)^k-\sum_{k=0}^n(-2)^k\\-3S&=(-2+4-8+\dots+(-2)^n+\color{red}{(-2)^{n+1}})-(\color{red}1-2+4-8+\dots+(-2)^n)\\-3S&=\color{red}{(-2)^{n+1}-1}+(2-2)+(4-4)+\dots\\-3S&=(-2)^{n+1}-1\\S&=\frac{(-2)^{n+1}}{-3}-\frac1{-3}=\left[\frac{(-2)^k}{-3}\right]_{k=0}^{k=n+1}\text{ or }\frac{(-2)^k}{-3}\Biggr|_0^{n+1}\end{align*} In general, the above argument shows that for $S=1+r+r^2+\dots+r^n$ we have $$S=\frac{r^{n+1}-1}{r-1}=\frac{r^k}{r-1}\Biggr|_0^{n+1}$$

For step (3), we merely expand:$$\frac{(-2)^k}{-3}\Biggr|_0^{n+1}=\frac{(-2)^{n+1}}{-3}-\frac{(-2)^0}{-3}=\frac{(-1)^{n+1} 2^{n+1}}{-3}-\frac1{-3}$$

In case you are unfamiliar with the notation, we write:$$F(k)\bigg|_a^b=F(b)-F(a)$$

-