How to calculate $\sum_{i = 0}^{k-1}\left(\frac{5}{6}\right)^i$

Question

I need to calculate the complexity of an algorithm. I have come across this summation that I can't evaluate, I am stuck. I haven't seen one of those in years, therefore I am rusty and really struggling:

$$\sum_{i = 0}^{k-1}\left(\frac{5}{6}\right)^i$$

where $k = \log_3(2n)$.

I have found several formulas, I am not sure which one I should apply:

$$\sum_{n=0}^{N}x^n=\frac{x^{N+1}-1}{x-1}$$

I don't think this is it, that would give me a negative value and since I am trying to calculate complexity, that can't be negative.

Perhaps I could use the formula for decreasing geometric series, so, I would have

$$\frac{1\cdot\left(1-\left(\frac{5}{6}\right)^k\right)}{1-\frac{5}{6}}$$

but then

$$\left(1-\left(\frac{5}{6}\right)^{\log_3{2n}}\right)\cdot 6$$

and I can't figure out how to get rid of that nasty exponent. Can please anyone put me on the right track?

why do you want to get rid of the exponent ?
$$ \frac{x^{n+1} - 1 }{x-1} = \frac{1 - x^{n+1}}{1-x} $$ — what'sup, Oct 14 '13 at 14:35
@what'sup because I need to show my algorithm is $\Theta(n)$ and I can't right now. — haunted85, Oct 14 '13 at 14:37

score 1 · Accepted Answer · answered Oct 14 '13 at 14:39

1

$a^{\log_b c}=\exp\left(\frac{\log a\log c}{\log b}\right) = c^{\log_b a}$
You have trouble with $(5/6)^{\log_3(2n)}$. The formula I gave shows how to turn it into a power of $n$.
Someone is having fun with their negativity button.

answered Oct 14 '13 at 14:39

Empy2

50,853

Compensated. Your argument is valid and explained, so I don't see why to -1 it... – AlexR Oct 14 '13 at 15:01
Thanks. First, I only gave the formula, which wasn't clear by itself. – Empy2 Oct 14 '13 at 15:03
Okay, didn't see that. Nice trick anyways ;-) – AlexR Oct 14 '13 at 15:03

How to calculate $\sum_{i = 0}^{k-1}\left(\frac{5}{6}\right)^i$

1 Answers1