Solving a recurrence relation. Check my answer I have a recurrence relation:

T(n)=4 for n&lt;=2
T(n)=3T(n/3)+5 for n&gt;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?
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) &amp;= \alpha_j &amp; \text{for }1\le j\lt d\\
f(dn+j) &amp;= cf(n)+\beta_j &amp; \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) &amp;= (\alpha_{b_m}\beta_{b_{m-1}}\beta_{b_{m-2}}\dots\beta_{b_1}\beta_{b_0})_c\\
&amp;= \underbrace{(4\;5\;5\dots5\;5)_3}_{m+1\text{ digits}}\\
&amp;= \underbrace{(5\;5\;5\dots5\;5)_3}_{m+1\text{ digits}} - 3^{m} \\
&amp;= 5\cdot \underbrace{(1\;1\dots1\;1)_3}_{m+1\text{ digits}} - 3^{m} \\
&amp;= 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$.)
Yes, that is correct. I don't see any problems with your answer.