Solving recurrence relations to find asymptotic behavior

Question

My goal is to solve the following recurrence relation so that I can find the asymptotic behavior of T(n): T(n) = 5T(n/3) + n. I've been able to almost solve but I'm just stuck in one particular step. $$ T(n) = 5T(n/3)+5$$ $$T(n/3)=5[5T(n/9)+(n/3)]+n$$ $$T(n/3)=25T(n/9)+(5n/3)+n$$ $$T(n/9) = 125T(n/27)+(25n/9)+(5n/3)+n$$ From here I was able to write the recurrence in series notation $$n\sum_{i=0}^{log_3n}{(5/3)^i}$$ Now here is where I get stuck. I'm stuck mostly in the algebra. By using the geometric series formula for a finite series I get $$\frac{1-(5/3)^{log_3n+1}}{1-(5/3)}$$ From here I just have to simplify it and get the asymptotic behavior(big O). I just don't know how to simplify it. If I can get a couple of examples or link as to how to do it, it would be greatly appreciated. Thanks.

Answer 1

Multiply top and bottom by $-1$ and use $$a^{\log_b n}=e^{c \ln n}=n^c$$via the change of log base formula.