# Solve recurrence relation.

I've got an recurrent function to solve.

$T_1 = 1$

$T_n = 2T_{\frac n2} + \frac{1}{2}n\log n$

I've got a tip to this excercise to determine additional variable as $k = 2^n$, where $k = 1, 2, 3, ...$

But after some calulations I'm wondering if $k=2^n$ can i say that $2^{k-1} = n - 1$ ?

I recieve following equation: $T_{2^k} = 2T_{2^{k-1}} + 2^{k-1}k*\log2$ , am i correct? What can i do next?

• To precise my question: how can i substitude $2^{k-1}$ and $2^k$ – Michael213 Feb 23 '18 at 18:08
• Define a new sequence, say $a_k = T_{2^k}$. In particular, $a_0=1$, and $a_k = 2 a_{k-1} + k 2^{k-1} \log(2)$. Now, compute $a_k$. Observe that I have presumed that $n$ is a power of $2$ only. – Math Lover Feb 23 '18 at 18:37
• After some calculations i recieve: $a_k = 2^{k-1}(2 + log2*k!)$ , and than : $T_{n} = 2^{n-1} * (2 + log2 * n!)$ which seems it is wrong answer. After computing for $n=1$ I dont get $T_1 = 1$. Have I made mistake ? – Michael213 Feb 23 '18 at 18:46

We can prove by induction that $$T_n = 2^kT_{\frac{n}{2^k}} + \frac{k}{2}n\log(n)-\sum_{i=0}^{k-1}\frac{in}{2}$$ This clearly holds for the base case $k = 1$. So assuming it holds for some $k$, we find: \begin{align} T_n &= 2^kT_{\frac{n}{2^k}}+\frac{k}{2}n\log(n) - \sum_{i=0}^{k-1}\frac{in}{2}\\ &= 2^k\left(2T_{\frac{n}{2^{k+1}}} + \frac{1}{2}\frac{n}{2^k}\log\left(\frac{n}{2^k}\right)\right)+\frac{k}{2}n\log(n) - \sum_{i=0}^{k-1}\frac{in}{2}\\ &=2^{k+1}T_{\frac{n}{2^{k+1}}} + \frac{n}{2}\log(n) - \frac{n}{2}\log(2^k)+\frac{k}{2}n\log(n) - \sum_{i=0}^{k-1}\frac{in}{2}\\ &= 2^{k+1}T_{\frac{n}{2^{k+1}}}+\frac{k+1}{2}n\log(n)-\sum_{i=0}^{k}\frac{in}{2} \end{align} So we have the claim. The sum has an easy closed form, so we may rewrite $T_n$ as: $$T_n = 2^kT_{\frac{n}{2^k}}+\frac{k}{2}n\log(n)-\frac{k(k-1)}{4}n$$ Letting $k= \log(n)$, we have: \begin{align} T_n&=nT_1+\frac{n}{2}\log^2(n)-\frac{n}{4}\log(n)(\log(n) - 1)\\ &=n + \frac{n}{4}\log^2(n)+\frac{n}{4}\log(n) \end{align}