How to deal with sum of $4^i$, from i to n, when the base isn't $2$?

Question

So guys, this is regarding complexity of algorithms. I'm trying to simplify:

$$\sum_{i=1}^{n}4^i$$

But I only know the simplification for $2^i$, from $1$ to $n$ (which is $2^{(i+1)}-2$.

Please can anyone guide me

Answer 1

HINT

Recall that for the geometric series for $|r|\neq 1$

$$\sum_{\color{red}{i=0}}^{n} r^i=\frac{r^{n+1}-1}{r-1}$$

indeed is easy to verify that

$$(1+r+r^2+\ldots+r^n)(r-1)=r^{n+1}-1$$

Answer 2

Let $S =\sum_{i=1}^n4^i$. Multiply both sides by 4 to get:

$S \cdot 4 = \sum_{i=2}^{n+1}4^i$

Subtract one from the other to get:

$S = \frac{4^{n+1}-4}{3}$