Leaving recurrence summation in terms of $k$, $\sum_{i=0}^{k-1}\frac{3^i\sqrt{\frac n{3^i}}}{\log\frac n{3^i}}$ I have an exercise where I need to use the substitution method to solve the following recurrence and determine their corresponding complexity.
$$t(n)=3t(n/3) + \frac{\sqrt n}{\log n}$$
After some iterations, I got the following pattern.
$$t(n)=t\left(\frac{n}{3^k}\right)+\sum_{i=0}^{k-1}\frac{3^i\sqrt{n/3^i}}{\log n/3^i}$$
Honestly I do not know what kind of approach I could use to solve the summation, and leave everything in terms of $k$.
 A: Hint 1. As regards the asymptotic analysis (complexity?), you may use the Master Theorem. Then $c_{crit}=\log_2(3)\approx 1.58$ and $f(n)=\frac{n^{1/2}}{\log(n)}\leq n^{1/2}$. What about $T(n)$?
Hint 2. Note that
$$t(2^n)=3^nt(1)+\sum_{k=0}^{n-1}\frac{3^k\sqrt{2^{n-k}}}{\log (2^{n-k})}
=3^nt(1)+3^n\sum_{k=1}^{n}\frac{(\sqrt{2}/3)^k}{k\log (2)}\sim C\cdot 3^n$$
because the series $\sum_{k=1}^{n}\frac{(\sqrt{2}/3)^k}{k\log (2)}$ is convergent (note that $\sqrt{2}/3<1$).
A: $$
t(2^{\log_2 n}) = 3 t\left(2^{\log_2\left(\frac u2\right)}\right)+\frac{\sqrt n}{\ln n}
$$
now calling $T(u) = t(2^u)$ with $u = \log_2 n$ we follow with
$$
T(u) = 3T(u-1) + \frac{2^{\frac u2}}{u\ln 2}
$$
This is a linear recurrence with solution $T(u) = T_h(u) + T_p(u)$
$$
\begin{cases}
T_h(u) = 3T_h(u-1) \\
T_p(u) = 3T_p(u-1) + \frac{2^{\frac u2}}{u\ln 2}
\end{cases}
$$
For the homogeneous we have
$$
T_h(u) = C_0 3^u
$$
and now making $T_p(u) = C_0(u) 3^u$ and substituting we have
$$
C_0(u)-C_0(u-1) = 3^{-u}\frac{2^{\frac u2}}{u\ln 2} = \frac{1}{\lambda}\frac{\alpha^u}{u}
$$
with $\alpha = \frac{\sqrt 2}{3} < 1$ and $\lambda = \ln 2$
so we have
$$
C_0(u) = \frac{1}{\lambda}\sum_{k=1}^{u}\frac{\alpha^k}{k}
$$
and then
$$
T(u) = \left(C_0+\frac{1}{\lambda}\sum_{k=1}^{u}\frac{\alpha^k}{k}\right)3^u
$$
hence
$$
t(n) = \left(C_0 + \frac{1}{\ln 2}\sum_{k=1}^{\log_2 n}\frac{\alpha^k}{k}\right)3^{\log_2 n}
$$
