TADM2E 2.29
From Algorithm Wiki
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} $
Therefore (c) is True. Note:
$ \begin{align} &3^{n+1}\\ &= 3\cdot3^{n}\\ &= 9\cdot3^{n-1}\\ \end{align} $
Consequently (a) and (b) are also true.
