Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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(T(n-3)+cn)+2cn = T(n-3)+3cn$



$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|cite|improve this question
You can follow this technique. – Mhenni Benghorbal Oct 20 '12 at 0:36
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|cite|improve this answer
Great answer, thanks very much! – mirai Oct 20 '12 at 1:21

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|cite|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

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|cite|improve this answer

An alternative solution:

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

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

share|cite|improve this answer

Your Answer


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.