1
$\begingroup$

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?

  • 0
    You can follow this [technique](http://math.stackexchange.com/questions/205372/how-to-solve-this-recurrence-relation-f-n-3f-n-1-12-1n/205491#205491).2012-10-20

4 Answers 4

4

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

  • 0
    Great answer, thanks very much!2012-10-20
0

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.

  • 0
    Sorry, I need to see how you solved it. The approach you linked doesn't really clarify it for me.2012-10-20
0

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

0

An alternative solution:

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

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