Solving the recurrence relation $T(n)=T(n-1)+cn$ 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?
 A: In your calculations, the placement of the parentheses is not correct. And for example it should be $T(n-1)=T(n-2)+c(n-1)$. 
One can travel from top down, or from bottom up. For this problem, I prefer bottom up. But it looks as if you are working top down, so I will do it that way. We have
$$T(n)=T(n-1)+nc.$$
But $T(n-1)=T(n-2)+(n-1)c$, so
$$T(n)=T(n-2)+(n-1)c+nc.$$
But $T(n-2)=T(n-3)+ (n-2)c$ and therefore
$$T(n)=T(n-3)+(n-2)c+(n-1)c+nc.$$
Continue. At the end we use $T(2)=T(1)+2c=1+2c$. We conclude that
$$T(n)=1+(2+3+\cdots +n)c.$$
Finally, use the standard fact that $1+2+\cdots +n=\frac{n(n+1)}{2}$, giving
$2+3+\cdots +n=\frac{n^2+n-2}{2}$. That gives
$$T(n)=1+\frac{n^2+n-2}{2}c.$$
One might want to note that $n^2+n-2=(n-1)(n+2)$. 
A: Here is your final solution
$$ T(n)= 1-c-c \left( n+1 \right) +c \left( n+1 \right)  \left( \frac{1}{2}\,n+1\right) \,.$$
For how to solve it you can follow this technique or that method. 
A: Suppose $T(n) = T(n-1)+f(n)$.
Then $T(n) = T(n-2) + f(n-1) + f(n)
= T(n-3) + f(n-2)+f(n-1)+f(n)
$.
Continuing by induction, for $k \le n$,
$T(n) = T(n-k)+\sum_{j=0}^{k-1} f(n-j)$. 
Letting $k = n-1$,
$T(n) = T(1)+\sum_{j=0}^{n-2} f(n-j)
= T(1)+\sum_{j=2}^{n} f(j)
$. 
If we know $T(m)$, we can get
$T(n)
= T(m)+\sum_{j=m+1}^{n} f(j)
$. 
In your case, since we know $T(1)=1$ and
$f(n) = cn$,
$T(n) = T(1)+\sum_{j=2}^{n} f(j)
= 1 + \sum_{j=2}^{n} cn
= 1 + c(\frac{n(n+1)}{2} - 1)
$.
A: An alternative solution:
$T(n) - T(n-1) = cn$
Sum from $n=2$ to $n=k$ since LHS is a telescoping sum.
