(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
The sum of a geometric sequence with a = 1, r = 3 (subtracting first term of $3^0 = 1$ since $i$ begins at 0) is:
\begin{align} &\sum_{i=1}^n 3^i\\ &= \frac{3^{n+1} - 1}{3-1} - 1 =\\ &= \frac{1}{2}{3^{n+1}} - \frac{3}{2} =\\ &= \Theta(3^{n+1}) \end{align}
\begin{align} &3^{n+1}\\ &= 3\cdot3^{n}\\ &= 9\cdot3^{n-1}\\ \end{align}