# Solve recurrence relation $T(n)=n^{1/5}T(n^{4/5})+5n/4$

I am trying to solve this recurrence relation - $$T(n)=n^{1/5}T(n^{4/5})+5n/4$$. I can't use the master's method and the recursion tree method because of that $$n^{1/5}$$ term.

We can write $$\frac{T(n)}n=\frac{T(n^{4/5})}{n^{4/5}}+\frac54$$

Now we can change variable $$S(n)=\frac{T(n)}{n}$$. So, we get $$S(n)=S(n^{4/5})+\frac{5}{4}$$

Then I used the recurrence tree method by taking $$n=2^{(\frac{5}{4})^k}$$. I got $$S(n)=O((log_{5/4}(log_2 n))^2)$$. So, $$T(n)=O(n(log_{5/4}(log_2 n))^2)$$

Thanks!

Lets consider $$n = 2^{(5/4)^k}$$. Now we can evaluate step by step: $$S(n) = S(2^{(5/4)^{k-1}}) + 5/4 = S(2^{(5/4)^{k-2}}) + 5/4 + 5/4$$ Notice that every time $$k$$ is reduced by one since: $$\left(2^{(5/4)^{k}}\right)^{4/5} = 2^{(5/4)^{k}\cdot(4/5)} = 2^{(5/4)^{k-1}}$$ Thus we can denote $$S(n)$$ as (assuming $$S(2) = 0$$ as base case): $$\sum_{i=1}^k 5/4 = (5/4)k$$ Now lets solve $$n = 2^{(5/4)^k}$$ for $$n$$. Apply $$\log_2$$ and then $$\log_{5/4}$$ on both sides: $$k = \log_{5/4}(\log_2(n))$$ and thus $$S(n) = (5/4)\log_{5/4}(\log_2(n))$$.
You can simply plug your solution in to test it. For $$S(n) = S(n^{4/5}) + 5/4$$ you can obtain $$S(n) = (5/4)\log_{5/4}(\log_2(n))$$ by the recursion tree method (as described above). Lets plug this into our recurrence: $$S(n) = (5/4)\log_{5/4}(\log_2(n^{4/5}))+5/4 = (5/4)\log_{5/4}((4/5)\log_2(n))+5/4$$ And by the rules of logaritm: $$S(n) = (5/4)\log_{5/4}(\log_2(n))+(5/4)\log_{5/4}(4/5)+5/4$$ Notice $$\log_{5/4}(4/5) = -1$$ and things cancel out: $$S(n) = (5/4)\log_{5/4}(\log_2(n))-(5/4)+5/4 = (5/4)\log_{5/4}(\log_2(n))$$ Our expression for $$S(n)$$ fulfills the recurrence. Hence $$T(n)/n = S(n) \Rightarrow T(n) = (5/4)n\log_{5/4}\log_2(n)$$ A double logarithm looks scary but if often occurs when recurrences have the form $$T(n) = aT(n^\alpha) +b$$.