1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ What did you try and where did you get stuck? $\endgroup$
    – Pål GD
    Jan 12 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$
    – user130726
    Jan 12 at 13:00
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy