T(n)=2T(n-1)+n-1, T(1)=1 , n>=2
T(n)=2kT(n-k)+2(k-1)(n-(k-1))+2(k-2)(n-(k-2))+.......+n
Now k=n-1
T(n)=2(n-1)(1)+2(n-2)(2)+2(n-3)(3)+.......+2(n-n)(n)
T(n)=2(n)[ 1/1 + 2/2(2) +3/2 (3) + 2/ 2(4) +....] + n
Now I am struck at this point how to proceed from here ?