# Difference between revisions of "TADM2E 2.29"

From Algorithm Wiki

(Recovering wiki) |
(Added solution) |
||

Line 1: | Line 1: | ||

− | + | The sum of a geometric sequence with a = 1, r = 3 (subtracting first term of <math>3^0 = 1</math> since <math>i</math> begins at 0) is: | |

+ | |||

+ | <math> | ||

+ | \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} | ||

+ | </math> | ||

+ | |||

+ | Therefore (c) is True. Note: | ||

+ | |||

+ | <math> | ||

+ | \begin{align} | ||

+ | |||

+ | &3^{n+1}\\ | ||

+ | &= 3\cdot3^{n}\\ | ||

+ | &= 9\cdot3^{n-1}\\ | ||

+ | |||

+ | \end{align} | ||

+ | </math> | ||

+ | |||

+ | Consequently (a) and (b) are also true. |

## Latest revision as of 08:29, 5 January 2015

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.