How we can prove that: $$ \sum_{k=1}^{c \log n-1}\:k\cdot \left(\frac{1}{2}\right)^{\frac{k}{3}}\in O\left(1\right) \quad \mbox{?} $$
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ What did you try and where did you get stuck? $\endgroup$– John KemenyCommented Jan 12, 2021 at 12:58
-
$\begingroup$ @PålGD I try to move $k$ outside from the serie but it didn't advance me to the solution, I don't think it's the right way... $\endgroup$– user130726Commented Jan 12, 2021 at 13:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
$$ \begin{align*} \sum_{k=1}^{c \log n - 1} k 2^{- \frac{k}{3}} &\le \sum_{k=1}^{c \log n } k 2^{- \lfloor \frac{k}{3} \rfloor } \le \sum_{k=1}^{\lceil \frac{c}{3} \log n \rceil} 3k 2^{-k+1} \le 6\sum_{k=0}^{\infty} k 2^{-k} \\ &\le 6\sum_{k=0}^{\infty} \left( \frac{3}{2} \right)^k 2^{-k} = 6 \sum_{k=0}^{\infty} \left( \frac{3}{4} \right)^k = 6 \cdot 4 = 24 \in O(1). \end{align*} $$
-
$\begingroup$ I have a small question. How you get $k < (3/2)^{k}$ in the $4^{th}$ inequality? $\endgroup$ Commented Jan 12, 2021 at 15:52
-
1$\begingroup$ No particular way, I wanted to upper bound $k$ with something of the form $\alpha^k$ with $\alpha < 2$ so the resulting series would be a geometric series that converges to a constant. I just picked a big enough values of $\alpha$ so that $k \le \alpha^k$ is true for every $k$. Other choices are possible too (and, in general, you can drop any constant number of the first terms from the series since they only contribute $O(1)$ to the result. Then, for any $\alpha>1$, you can look at sufficiently large values of $k$ for which $k \le \alpha^k$ holds). $\endgroup$– StevenCommented Jan 12, 2021 at 15:54
-