Solving $a_n=5a(n/3)-6a(n/9)+2log_3n$ using domain transformation $a_n=5a(n/3)-6a(n/9)+2log_3n$, For $n\ge9$ and n is a power of 3.
$a_3=1$, and $a_1=0$
Transforming the first two terms is straightforward, but I'm not sure what to do with the log term. Should I rewrite it somehow? The fact that it isn't attached to the function, but just to n, is also somewhat confusing.
 A: Since $n\geq 9$ is a power of 3, we will write $n=3^x$ for variable $x\geq 2$.  Substitute this into your recurrence, and you get $$a(3^x)=5a(3^{x-1})-6a(3^{x-2})+2x.$$  Now we define a new recurrence in terms of the variable $x$ as follows: define the function $a^*:x\mapsto a(3^x)$.  Then, by the recurrence above, $a^*(x)$ satisfies the recurrence $$a^*(x)=5a^*(x-1)-6a^*(x-2)+2x.$$  Your initial conditions $a_3=1$ and $a_1=0$ become $a^*_1=1$, $a^*_0=0$.  The above recurrence is linear, so can be solved using the usual methods.
A: Let $b_n:=a_{3^n}$. Then $b_{n}=5b_{n-1}-6b_{n-2}+2n$. Afterall, $\log_3(3^n)=n$. Can you solve it now?
A: Here is a  closely related recurrence that has  the same complexity as
the  one in the  OP and  admits an  exact solution  for all  $n.$ This
computation         resembles        the         following        MSE
link, the difference
being that this one does not depend on the digits of $n.$
Suppose we start by solving the following recurrence for $n\ge 3$:
$$T(n) = 5 T(\lfloor n/3 \rfloor) - 6 T(\lfloor n/9 \rfloor) + 
\lfloor \log_3 n \rfloor$$
where $T(0) = 0$ and $T(1) = T(2) = 1.$
We unroll the recursion to obtain an exact formula for $n\ge 3$
$$T(n) = [z^{\lfloor \log_3 n \rfloor}] \frac{1}{1- 5 z+ 6 z^2} +
\sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 
[z^j] \frac{1}{1- 5 z+ 6 z^2}
(\lfloor \log_3 n \rfloor - j).$$
where the first  term represents the base cases with  $n\lt 3$ and the
second the contribution from the logarithmic term.
Observe that the roots of $$1- 5 z + 6 z^2
\quad\text{are}\quad\rho_0=\frac{1}{2}
\quad\text{and}\quad\rho_1=\frac{1}{3}$$
and $$\frac{1}{1- 5 z+ 6 z^2} 
= \frac{3}{1-3z} - \frac{2}{1-2z}.$$
It follows that the coefficients of the rational term have the form
$$[z^j] \frac{1}{1-5z+6z^2} 
= 3^{j+1} - 2^{j+1}.$$
This gives the exact formula for $T(n):$
$$T(n) = 3^{\lfloor \log_3 n \rfloor+1} 
- 2^{\lfloor \log_3 n \rfloor+1}
+ \sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 
(3^{j+1}-2^{j+1}) 
(\lfloor \log_3 n \rfloor - j)
\\ = 3\times 3^{\lfloor \log_3 n \rfloor} 
- 2\times 2^{\lfloor \log_3 n \rfloor}
\\ + \frac{9}{4} 3^{\lfloor \log_3 n \rfloor} 
- \frac{3}{2} \lfloor \log_3 n \rfloor
- \frac{9}{4}
\\ - 4 \times 2^{\lfloor \log_3 n \rfloor} 
+ 2\times \lfloor \log_3 n \rfloor
+ 4$$
which simplifies to
$$\frac{21}{4} 3^{\lfloor \log_3 n \rfloor}
- 6 \times 2^{\lfloor \log_3 n \rfloor}
+ \frac{1}{2} \lfloor \log_3 n \rfloor 
+ \frac{7}{4}.$$
It follows that $T(n)$ has the dominant asymptotic
$$T(n)\in\Theta\left(3^{\lfloor \log_3 n \rfloor}\right)
= \Theta\left(3^{\log_3 n}\right)
= \Theta(n).$$
Observe that $5/3-6/9= 5/3-2/3=3/3=1,$ which checks.
Here is another Master Theorem computation at MSE.
