Solving a recurrence relation using repeated substitution

Question

So, basically I am having a big issue with this recurrence relationship:

$$T(n) = T(n-1)+n, T(1) = 0$$

using repeated substitution I get down to:

$$i=1, T(n-1) + n$$

$$i=2, T(n-2) + 2n - 2$$

$$i=3, T(n-3) + 3n - 3$$

$$T(n) = T(n-i) + i*n - i$$

Base case: $n-i = 1, i.e. i = n - 1$

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

$$T(n) = n^2 - 2n + 1 $$

But, wolframalpha gives me:

$$T(n) = 0.5*n^2 + 0.5*n + c$$

And with $T(1) = 0$:

$$T(n) = 0.5*n^2 + 0.5*n - 1$$

Am I doing something wrong??

Please help!!

Answer 1

You seem to be off by 1

$$T(n) = T(n-1) + n = T(n-2) + n -1+n = T(n-2) + 2n-1$$

And you have $2n-2$. The next step gives

$$T(n) = T(n-3) + n-2 + 2n-1 = T(n-3) + 3n - 3$$

And one more gives

$$T(n) = T(n-4) + n-3 +3n-3 = T(n-4) + 4n -6$$

In geeneal the constant term will be the sum from $1$ to $k-1$ of $k$. In this case $6 = 1+2+3$. I'm sure you can find the right formula.

Answer 2

You have applied the formula incorrectly.

If $T(n)=T(n-1)+n$, then we have

$$T(n-1)=T(n-2)+n-1$$

(Note that we have substituted $n-1$ into the original equation in place of $n$.)

Further, we have

$$T(n-2)=T(n-3)+n-2$$

So if we apply multiple-substitution, we have

$$T(n)=T(n-1)+n=T(n-2)+n-1+n=T(n-3)+n-2+n-1+n=\cdots$$

Can you come up with a simpler expression which correctly conveys this value? Are you familiar with the sum over $n$ consecutive integers?