# Asymptotic growth of a series

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{?}$$

• What did you try and where did you get stuck? – Pål GD Jan 12 at 12:58
• @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... – Xavi Jan 12 at 13:00

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

• I have a small question. How you get $k < (3/2)^{k}$ in the $4^{th}$ inequality? – Inuyasha Yagami Jan 12 at 15:52
• 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). – Steven Jan 12 at 15:54
• I get it. nice trick! – Inuyasha Yagami Jan 12 at 16:01