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.
