$n + (1/2)n + (1/2)^2n + (1/2)^3n + ... + (1/2)^{log_2n}n$
Doesn't get me anywhere if I apply sum of a GP. Kind of stuck at this step.
Asked
Active
Viewed 325 times
0
trickster
- 39
-
1If you rewrite it as $n\sum_{k=0}^{\log_2 n} \left(\frac{1}{2}\right)^k,$ can you see how to calculate it? – Antonio Vargas Jun 05 '18 at 04:52
-
Nope. My best guess will be to come up with some rough estimation for the summation. – trickster Jun 05 '18 at 04:58
1 Answers
0
Lets start by writing your expression as a sum, as suggested in the comments by Antonio Vargas:
$$n\sum_{k=0}^{\log _2n}\left(\frac{1}{2}\right)^2$$
Now lets consider the sum without including the outer $n$. Lets also take the limit where $\log _2n$ goes to infinity:
$$\lim_{\log _2n\rightarrow\infty}\sum_{k=0}^{\log _2n}\left(\frac{1}{2}\right)^2=2$$
The above sum is something you might have seen before, and as we know it will be equal to two. Now we have an upper bound of the original expression, i.e.:
$$n\sum_{k=0}^{\log _2n}\left(\frac{1}{2}\right)^2 \le n\lim_{\log _2n\rightarrow\infty}\sum_{k=0}^{\log _2n}\left(\frac{1}{2}\right)^2=2n$$
Erik Kjellgren
- 171