Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
You can follow this technique. –  Mhenni Benghorbal Oct 20 '12 at 0:36
add comment

4 Answers 4

up vote 4 down vote accepted

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

share|improve this answer
    
Great answer, thanks very much! –  mirai Oct 20 '12 at 1:21
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

An alternative solution:

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

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.