I've solved the recurrence relation $T(n)=T(n-1)+cn$ (where T(1)=1), getting $1+c(\frac{n(n+1)}{2}-1)$, but I can't seem to get the pre-replacement step involving $k$.
Here's what I have:
$T(n-1)+cn$
$T(T(n-2)+cn)+cn=T(n-2)+2cn$
$T(T(n-3)+cn)+2cn = T(n-3)+3cn$
$\dots$
$T(n-k)+kcn$
$k=n-1$, so the post-replacement step is $T(1)+(n-1)cn$
This is wrong, however, since $T(3)=1+5c$, whereas $T(1)+(3-1)(3)c=1+6c$
What am I doing wrong here?