Solve $T(n)=2T(\frac{n}3)+\log_3(n)$ for n>1, n a power of 3 Solve the following recurrence equation using the characteristic equation.
$T(n)=2T(\frac{n}3)+\log_{3}n$ for $n>1$, $n$ a power of $3$
$T(1)=1$
I'm not quite sure I understand exactly what to do here. I've done this much on my own
Let $n=3^k$, $k=\log_{3}n$
$T(3^k)=2T(\frac{3^k}{3})+k$
$T(3^k)=2T(3^{k-1})+k$
Let $t_{k}=T(3^k)$
$t_{k}=2t_{k-1}+k$
But that's as far as I can get. After that, I'm completely lost. Even when I'm trying to follow the example in the book, it seems like either a lot of intermediate steps are skipped or the example doesn't fit my question. Any assistance would be appreciated.
 A: We can actually solve this recurrence exactly and not just for powers of three, at any rate one that is very close. Consider
$$T(n) = 2 \; T(\lfloor n/3\rfloor) + \lfloor\log_3 n\rfloor+1$$
with $T(0) = 0$ and which has $T(1) = 1.$ The constant one has lower order than the logarithm so the complexity is the same as in the original query. (Note $|\lfloor\log_3 n\rfloor-\log_3 n | < 1$ and that $|\lfloor\log_3 n\rfloor+1-\log_3 n | < 1$ so adding in one introduces the same error as using the floor alone.)
The key observation is that the answer does not depend on $n$ but only on the number of digits in base three that it has, i.e. the logarithm.
If $$n= \sum_{k=0}^{\lfloor\log_3 n\rfloor} d_k 3^k
\quad\text{then}\quad
T(n) = \sum_{k=0}^{\lfloor\log_3 n\rfloor} 2^k \; (\lfloor\log_3 n\rfloor+1-k)
= 4 \times 2^{\lfloor\log_3 n\rfloor} -\lfloor\log_3 n\rfloor -3.$$ 
This formula is exact for all $n.$
Now clearly the dominant term is the exponential one which gives the following complexity:
$$\Theta\left(2^{\lfloor\log_3 n\rfloor}\right) =
\Theta\left(3^{\log_3 2 \times \lfloor\log_3 n\rfloor}\right) =
\Theta(n^{\log_3 2}).$$
This is of course the same as what the Master theorem would produce. Here is another calculation of the same type  that is a bit more advanced.
A: Look carefully and I think you can see that $t_{n+1}$ = $t_n + 3$.  Now run that observation back to T(1)  = 1 $\Rightarrow t_1 = 1$.  At this point you should be able to write $t_n$ just in terms of n and without any other t's.
A: You have $t_k - 2t_{k-1} = k$ with the condition $t_0 = 1$ (why?)
The characteristic equation would have been  $x-2 = 0$ if the equation was homogeneous (i.e. RHS was $0$). This would have given us the solution $t_k = a 2^k$.  However given that there is a linear function in the RHS, we should explore solutions of form $t_k = a 2^k + (bk + c)$.
Substitute in the recurrence and see if we can find values for $b, c$ s.t. the recurrence holds for all $k$.  Then use the initial condition to find $a$...   
