# Summation over exponent $\sum_{i=0}^k 4^i= \frac{4^{k+1}-1}3$

Why does $\sum_{i=0}^k 4^i= \frac{4^{k+1}-1}3$, where does that 3 comes from?

Ok, from your answers I looked it up on wikipedia Geometric Progression, but to derive the formula it says to multiply by $(1-r)$ not $(r-1)$ why is this case different?

-
Is c equal to 2 ? – Amr Nov 13 '12 at 1:43
Its equal to 4, my mistake. – zad Nov 13 '12 at 1:43
you meant $4^k$ not $4^2$ – Amr Nov 13 '12 at 1:44
Yes $4^i$, I edited the question. – zad Nov 13 '12 at 1:45

The other answers are correct, this is the finite geometric series for $r=4$. You asked why this is so, and in fact, this is not too difficult to derive. Let $S$ be the sum we want to evaluate, which means

$S=1+r+r^2+r^3+\ldots+r^n$

If we multiply by $r$,

$rS=r+r^2+r^3+\ldots+r^n+r^{n+1}$

Now subtract

$rS-S = S(r-1) = r^{n+1}-1$

$\Longrightarrow S= \dfrac{r^{n+1}-1}{r-1}$.

So for your series, evaluating this for $r=4$ gives $S=\dfrac{4^{n+1}-1}{4-1}$. Thus the $3$ comes from the $r-1$ term in the denominator.

Note: In the final step we are dividing by $r-1$, so this formula is no longer valid if $r=1$, since we cannot divide by zero.

Comment response: In the way it's done on Wikipedia, the sum is $S=\dfrac{1-r^{n+1}}{1-r}$, and actually this is equivalent to what I wrote. Note that $(1-r^{n+1})=-(r^{n+1}-1)$ and the same goes for the denominator; $1-r = -(r-1)$. So since the sign of the terms change on both top and bottom, the fraction remains the same. Thus both expressions are equivalent.

-
So, I looked it up in wikipedia and the formula is a little different, the subtraction is the other way around $(1-r)$ why is this case different? – zad Nov 13 '12 at 2:11
I've added a response to this question in my answer above. – leeabarnett Nov 13 '12 at 2:17

It comes from the formula for a finite geometric series: $3 = 4 - 1$, and for any $r \ne 1$ $$\sum_{i=0}^k r^i = \frac{r^{k+1}-1}{r-1}$$

-

It’s just the standard formula for the sum of a geometric series. In case you’ve not seen a derivation, let $S=\sum_{i=0}^k4^i$; then

\begin{align*} S&=1+\color{red}{4+4^2+\ldots+4^k}\\ 4S&=\quad\;\;\, \color{red}{4+4^2+\ldots+4^k}+4^{k+1}\;, \end{align*}

and if you subtract the top equation from the bottom one you get $3S=4^{k+1}-1$, since the red terms cancel out. Now just solve for $S$.

This same argument will give you the general formula:

$$\sum_{i=k}^nr^i=\frac{r^{n+1}-r^k}{r-1}\;.$$

-
So, I looked it up in wikipedia and the formula is a little different, the subtraction is the other way around $(1-r)$ why is this case different? – zad Nov 13 '12 at 2:11
@zad: It isn’t any different. In the formula that you found, the subtraction in the numerator is also reversed. $$\frac{r^{n+1}-r^k}{r-1}=\frac{r^{n+1}-r^k}{r-1}\cdot\frac{-1}{-1}=\frac{r^k - r^{n+1}}{1-r}\;,$$ so they’re exactly the same formula in slightly different arrangements. – Brian M. Scott Nov 13 '12 at 2:21

Here is an easy mnemonic. If you have a geometric sum, then

$$\sum {\rm geometric} = {{\rm first} - {\rm last}\over {1 - {\rm common \ Ratio}}}.$$

In this case, first is the first term, blast is the one beyond the last, and commonRatio is the common ratio of the terms. If the sum is finite and ${\rm commonRatio} > 1$, reverse the subtractions in the numerator and denominator for greater prettiness.

-
That's a nice way to remember it. +1 – Thomas Nov 13 '12 at 8:02

Recall that $$\sum\limits_{i = 0}^k {a{r^i} = a + ar + a{r^2} + \ldots + a{r^k} = a\frac{{{r^{k + 1}} - 1}}{{r - 1}}}$$ (see my answer to this question if you wish to prove the above result).

-