TADM2E 2.29

From Algorithm Wiki
Revision as of 08:29, 5 January 2015 by Soroushjp (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.