I have the below recurrence:
$$T(n, 1) = 3n$$
$$T(1, m) = 3m$$
$$T(n, m) = 3n + T \left( \frac{n}{3}, \frac{m}{3} \right )$$
How to get a tight asymptotic bound for $T(n, n^2)$ assuming that $n$ is an exponent of $3$. Using substitution method for $T(m,n)$, I get a very weird relation
$$T(n,m) = 3n + \frac{m}{3^{k-1}} + n \left [ 3 - \frac{1}{3^{k-1}} \right ]$$
Any suggestion would be helpful
Hint:
You might define a new relation $S(p,q) \triangleq T(3^p, 3^q)$. This gives you a new recurrence:
$$S(p,0) = 3^{p+1}$$ $$S(0,q) = 3^{q+1}$$ $$S(p,q) = 3^{p+1} + S(p-1,q-1)$$
(do you see why?)
After making this change, your case of interest, $T(n,n^2)$, becomes $S(p,2p)$ (do you see why?) and it's quite easy to compute a closed form for this. Notice $p < 2p$, so we know which base case is relevant for us! Then it's just a matter of setting $n = 3^p$ in your closed form for $S(p,2p)$ to get a closed form for $T(n,n^2)$.
As for asymptotics, the closed form you get from the above procedure is so nice I'm not sure you need anything fancier.
I hope this helps ^_^