Solution of a recurrence equations $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!

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)$.
