Solving a recurrence relation. Check my answer I have a recurrence relation:
T(n)=4 for n<=2
T(n)=3T(n/3)+5 for n>2

So I began solving it,
T(n/3)=3T(n/9)+5
then 
T(n)=3(3T(n/9)+5)+5
= 3^k T(n/3^k)+5k
letting k=log_3_n
= 3^log_3_n T(n/3^log_3_n)+5log_3_n
= nT(1)+5log_3_n
= 4n+5log_3_n

Is this the correct answer?
I am confused on the part where there is +5k. Is that part correct?
 A: This is a generalized Josephus recurrence, of which an in-depth solution is given in Concrete Mathematics (by Graham, Knuth, Patashnik).

If $f$ is defined as:
$$\begin{align}f(j) &= \alpha_j & \text{for }1\le j\lt d\\
f(dn+j) &= cf(n)+\beta_j & \text{for } 0 \le j \lt d\text{ and } n\ge 1
\end{align}$$
Then $f\left((b_mb_{m-1}\dots b_1b_0)_d\right) = (\alpha_{b_m}\beta_{b_{m-1}}\beta_{b_{m-2}}\dots\beta_{b_1}\beta_{b_0})_c$
  (where $(b_mb_{m-1}\dots b_1b_0)_d$ is the radix-$d$ representation of $n$).

Applied to your problem, we have $d = 3$, $\alpha_j = 4$, $c = 3$, and $\beta_j = 5$.
Thus, your solution is:
$$\begin{align}
f\left((b_mb_{m-1}\dots b_1b_0)_d\right) &= (\alpha_{b_m}\beta_{b_{m-1}}\beta_{b_{m-2}}\dots\beta_{b_1}\beta_{b_0})_c\\
&= \underbrace{(4\;5\;5\dots5\;5)_3}_{m+1\text{ digits}}\\
&= \underbrace{(5\;5\;5\dots5\;5)_3}_{m+1\text{ digits}} - 3^{m} \\
&= 5\cdot \underbrace{(1\;1\dots1\;1)_3}_{m+1\text{ digits}} - 3^{m} \\
&= 5\left(\frac{3^{m+1}-1}{2}\right) - 3^{m}
\end{align}$$
(Where $m+1$ is the number of digits in the base-$3$ representation of $n$.)
A: Yes, that is correct. I don't see any problems with your answer.
