Express square root in terms of log 10

Question

I’m trying to help my son with some revision. One of his revision questions uses a formula $$T(n) = 4T(n^\frac{1}{2}) + \log_{10} n$$ To solve the problem he needs to express the $n^\frac{1}{2}$ in the form $\frac{n}{b}$. There’s a hint to define $k = \log_{10} n$, but I’m struggling to see how this helps. Is there a way to rewrite that square root of n using log? I’ve tried expanding it in different ways, but I think I’m missing something fundamental

Answer 1

If $T(n) = 4T(n^\frac{1}{2}) + \log_{10} n $, let $n=2^{2^m}$ so that $2^m=\log_2(n) $.

This works because $(2^{2^m})^{1/2} =2^{2^m/2} =2^{2^{m-1}} $.

Then

$T(2^{2^m}) = 4T((2^{2^m})^\frac{1}{2}) + \log_{10} 2^{2^m} = 4T(2^{2^{m-1}}) + 2^m\log_{10} 2 $.

Now, let $U(m) =T(2^{2^m}) $. This becomes $U(m) =4U(m-1)+\log_2(m)\log_{10}(2) =4U(m-1)+\log_{10}(m) $.

You should be able to solve this for $U$.

Then replace $m$ by $2^{2^m}$ to get $T$.