I'm trying to find a closed form (non-recursive equation using telescoping method and this is what I tried. I ended up with
$$T(n) = \frac{2N}{2^{k-1}} +kN^2$$
I tried to verify this and it doesn't seem right. $N = 1, k = 0$ (since we allowed $N=2^k$) $$T(1) = 1$$ but using the closed form that I found $$T(1) = \frac{2}{2^{-1}} + 0 = 4 $$
I've been trying to find a mistake but I'm stuck.. Could you give me a hint how I can improved this ? Thank you for your help.
$T(n) =4T(n/2)+n^2 $, $T(1) = 1$.
Let $n = 2^m$. Then $T(2^m) =4T(2^{m-1})+(2^m)^2 $, $T(2^0) = 1$.
Let $u(m) =T(2^m) $.
Then $u(m) =4u(m-1)+4^m, u(0) = 1 $.
Dividing by $4^{m}$, this becomes $\frac{u(m)}{4^m} =\frac{u(m-1)}{4^{m-1}}+1, u(0) = 1 $.
Let $v(m) = \frac{u(m)}{4^m}$. Then $v(m) = v(m-1)+1, v(0) = 1$.
This is easily seen to imply that $v(m) = m+1$.
To see this, write it as $v(m)-v(m-1) = 1$. Summing this from $1$ to $m$, the left side gives (here's the telescoping) $\sum_{k=1}^m (v(k)-v(k-1)) =v(m)-v(0) $ and the right side gives $\sum_{k=1}^m1 =m $, so $v(m)-v(0) = m$ or, since $v(0) = 1$, $v(m) = m+1$.
Unwinding, $u(m) = 4^mv(m) = (m+1)4^m $ and then $T(2^m) =u(m) = (m+1)4^m $.
If $n = 2^m$, then $m = \log_2 n$ and $4^m = n^2$, so $T(n) =(m+1)4^m =(1+\log_2n)n^2 $.
As a check,
$\begin{array}\\ 4T(n/2)+n^2 &=4((1+\log_2(n/2))(n/2)^2)+n^2\\ &=4((1+\log_2n-\log_22)n^2/4)+n^2\\ &=(1+\log_2n-1)n^2)+n^2\\ &=(\log_2n)n^2+n^2\\ &=(1+\log_2n)n^2\\ &=T(n)\\ \end{array} $