How can I solve this recursive relation?

Question

If $T(1)=1 $ and $nT(n)=2nT(n/2)+n^2,n>1$ find $ T(n)$. I have tried both changing the variable $n$ to $2x$ or something similar, but I get to a dead end, since I can not deal with odd values of n this way. How could I proceed? Thanks in advance.

Answer 1

Write $n = m \cdot 2^k$, with $m$ odd and show (induction on $k$) that $T(m\cdot 2^k) = 2^k(km+T(m)).$ That's the most you can do, since for $m>1$ and odd, $T(m)$ can take any value ...

[Added] This addition addresses the version of the problem proposed by @NobleMushtak: $T(n) = n + 2T(\lfloor n/2\rfloor])$, $T(1) = 1$.

Consider the binary representation of $n$, given by $n = a_0 + 2a_1 + 2^2 a_2 + \dotsb + 2^{k-1}a_{k-1} + 2^k$. Then $T(n) = n + 2T\left( \frac{n-a_0}{2}\right)$; one can use this to show, by induction on $k$, that $$T(2^0a_0 + 2^1a_1 + 2^2 a_2 + \dotsb + 2^{k-1}a_{k-1} + 2^k) = 1\cdot 2^0a_0 + 2\cdot 2^1 a_1 + 3\cdot 2^2 a_2 + \dotsb + k\cdot 2^{k-1}a_{k-1} + (k+1)\cdot 2^k$$

Answer 2

First, notice that $T(n/2)$ is the same for $n=m$ and $n=m+1$ where $m$ is even. Since $T(m)=2*T(m/2)+n$, this means $T(m+1)=2*T(m/2)+m+1$ and subtracting the two equations gives us $T(m+1)-T(m)=1$. Thus, if we know all $T(m)$ for even $m$, we can figure out all of the odd inputs by adding the output of the preceding even input by $1$.

Now, let's say $m/2$ is odd, meaning $\frac{m-2}{2}=m/2-1$ is even. By the above, we have $T(m/2)=T(m/2-1)+1$, and thus: $$T(m)=2\cdot T(m/2)+m=2\cdot (T(m/2-1)+1)+m \\ =2\cdot T(\frac{m-2}{2})+m+2=2\cdot T(\frac{m-2}{2})+(m-2)+4=T(m-2)+4$$ Thus, $T(m)-T(m-2)=4$ for even $m$ where $m/2$ is odd.

Now, let's say $m/4$ is odd, meaning $m/2$ is even, but $(m/2)/2$ is odd. By the above, we have $T(m/2)-T(m/2-2)=4$ and that $T(m/2-1)-T(m/2)=1$, so we get $T(m/2)-T(m/2-1)=3$. Thus: $$T(m)=2\cdot T(m/2)+m=2\cdot (T(m/2-1)+3)+m \\ =2\cdot T(\frac{m-2}{2})+m+6=2\cdot T(\frac{m-2}{2})+(m-2)+8=T(m-2)+8$$

Thus, we get $T(m)-T(m-2)=8$ for even $m$ where $m/4$ is odd.

Hopefully, you see the pattern here. $T(m)-T(m-2)=2^{k+1}$ where $\frac{m}{2^k}$ is odd. Thus, for $l=2,6,10,... < n$, we are adding $4$ to $T(n)$. There are $\lfloor \frac{n+2}{4} \rfloor$ such $m$s. Then, for $m=4,12,20,... < n$, we are adding $8$ to $T(n)$. There are $\lfloor \frac{n+4}{8} \rfloor$ such $m$s. Thus, the pattern is that the number of $m$s that add $2^{k+1}$ to $T(n)$ is $\lfloor \frac{n+2^k}{2^{k+1}} \rfloor$, giving us: $$T(n)=\sum_{k=1}^\infty \lfloor \frac{n+2^k}{2^{k+1}}\rfloor2^{k+1}$$ Note that this only works for even $n$ and we need to add $1$ for odd $n$, as shown at the top of this answer. Also, I do not know how to simplify this sum, but hopefully, you can take it from here. Good luck!