Solving a recurrence relation: $T(n^6) = 9T(n^{\frac{1}{6}}) + \log^2(n)$

Question

I would like to solve the relation:

$T(n^6) = 9T(n^{\frac{1}{6}}) + \log^2_2(n)$

Now upon searching, I found that such relations can be solved using iteration method and making a substitution, hence I tried substituting $m = \log_2 n$. This gives the relation:

$T(64^m) = 9T(2^{\frac{m}{6}})+m^2$. Am I solving this correctly?? How do I proceed further? Please help, I am not good at this.

Answer 1

$T(n^6) = 9T(n^{\frac{1}{6}}) + \log^2_2(n) $

Put $n = 2^{2^m} $. $\log_2n = 2^m $.

Becomes $T((2^{2^m})^6) = 9T((2^{2^m})^{\frac{1}{6}}) + 2^{2m} $ or $T(2^{6\cdot 2^m}) = 9T(2^{2^m/6}) + 2^{2m} $.

Try $n = 2^{6^m} $. $\log_2n = 6^m $.

Becomes $T((2^{6^m})^6) = 9T((2^{6^m})^{\frac{1}{6}}) + 6^{2m} $ or $T(2^{6^{m+1}}) = 9T(2^{6^{m-1}}) + 6^{2m} $.

Let $U(m) =T(2^{6^m}) $. Then $U(m+1) = 9U(m-1) + 6^{2m} $.

This is readily solved.