Stuck in recurrence relation

Question

$T(n) = 2 T\left(\dfrac{n}{2}\right) + n (\log_{2}n)^{2}, n > 1$

$T(1) = 1$

Note : $(\log_{2}n)^{2} = \log_2 n \times \log_2 n$

I have solve the above equation till the step

$T(n) = 2^{k} T\left(\dfrac{n}{2^k}\right) + n \sum_{i = 0}^{k-1} \left(\log_{2} \dfrac{n}{2^{i}}\right)^2$

However I am unable to solve $\sum_{i = 0}^{k-1} \left(\log_{2} \dfrac{n}{2^{i}}\right)^2$

Answer 1

Making $n=2^z$ we have

$$ \mathbb T(z)=2\mathbb T(z-1)+2^z z^2 $$

with solution

$$ \mathbb T (z) = \frac 13 2^{z-1}\left(z+3z^2+2z^3+3C_0\right) $$

and finally $\mathbb T (z)\to T(n)$

$$ T(n) = \frac n2C_0 + \frac n6 \log_2 n+\frac n2 (\log_2 n)^2+\frac n3(\log_2 n)^3 $$

NOTE

$$ \mathbb T (u) = T(2^u) $$

$$ T(n) = T\left(2^{\log_2 n}\right) = T\left(2^z\right) = \mathbb T(z) $$

Answer 2

Try the Ansatz $T(n)=kn\log_2^3n$ so $$T(n)-2\left(\frac{n}{2}\right)=kn\left(\log_2^3n-(\log_2n-1)^3\right)\approx 3kn\log_2^2n,$$so take $k=\frac13$.