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?
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?
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}\;.$
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.
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.