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?

-
You can follow this technique. –  Mhenni Benghorbal Oct 20 '12 at 0:36

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)$.

-
Great answer, thanks very much! –  mirai Oct 20 '12 at 1:21

$$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.

-
Sorry, I need to see how you solved it. The approach you linked doesn't really clarify it for me. –  mirai Oct 20 '12 at 0:43

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)$.

-

An alternative solution:

$T(n) - T(n-1) = cn$

Sum from $n=2$ to $n=k$ since LHS is a telescoping sum.

-