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$ – Xavi 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$ – Inuyasha Yagami 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$ – Inuyasha Yagami Jan 12 at 16:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.