Solving a recurrence relation. Check my answer

Question

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?

Answer 1

Yes, that is correct. I don't see any problems with your answer.

Answer 2

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