Solution of a recurrence equations

Question

$T(1) = 1$

$T(n) = 2T(\frac{n}{3}) + n + 1$

How do you solve this equzione recurrence? I arrived at this point and then I don't know how to proceed...

$2^kT(\frac{n}{3^k}) + \frac{2^{k-1}n}{3^{k-1}} + 2^{k-1} + \frac{2^{k-2}n}{3^{k-2}} + 2^{k-2} + \frac{2n}{3} + 2 + 1$

Thanks a lot!

Answer 1

Use the Master Method:

$T(n) = 2T(\frac{n}3) + n + 1$ falls into Case 3, because $c > \log_{b}(a)$, with $c=1$, $a=2$, $b=3$, $f(n) = n+1$. Additionally $af(\frac{n}{b}) \leq kf(n)$ is trivially satisfied with $k = \frac{2}{3}$.

Thus, $T(n) = \Theta(f(n)) = \Theta(n)$.