this is a example from my book
Write several elements of the recursion, and see if you can find a pattern.
T(n) = T(n – 1) + n
T(n –1) = T(n – 2) + (n –1)
T(n –2) = T(n – 3) + (n –2)
T(n –3) = T(n – 4) + (n –3)
Now substitute:
T(n) = T(n – 1) + n
= [T(n – 2) + (n –1)] + n
= [[T(n – 3) + (n –2)] +(n –1)] + n
= [[[T(n – 4) + (n –3)] + (n –2)] +(n –1)] + n
= T(n – k) + Σki=1(n –i+1) = T(n – k) + nk – ((k – 1)k)/2
I dont understand how they got
T(n – k) + nk – ((k – 1)k)/2
How did they go from this line
= [[[T(n – 4) + (n –3)] + (n –2)] +(n –1)] + n
to
= T(n – k) + Σki=1(n –i+1) = T(n – k) + nk – ((k – 1)k)/2
?