Algorithms recurrence relation

Question

Base condition T(n) = 1

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

Then

After solving i got to this step ...how should i generalize now

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

Answer 1

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

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

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

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

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

T(n)=T(n-k) +n*k -(1+2+3....k);

now at k=n we get T(0)=1;

so T(n)=T(0)+n*n- (1+2+3....n);

we get n^2-n(n+1)/2

T(n)=O(n^2)

Comments

T(n)=T(n-k) +n*k -(1+2+3....k);

Pls how you took n*k

---

When we substitute values for T(n), at one step we got

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

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

      =T(n-k) + n*k -(1+2+3+...k)

---

Thanks that really helped