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
?
The line just above "I don't understand how they got" is incorrect (or at least confusing). You have the pattern $$\begin{align} 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 \end{align}$$ and it appears that $$ T(n)=T(n-k)+[(\color{red}{n-k}+1)+(\color{red}{n-k}+2)+\cdots+(n-1)+n] $$ We can write the part in brackets as $$ \sum_{i=1}^k(n-k+i) $$ and recognize that this is $$ \sum_{i=1}^k(n-k)+\sum_{i=1}^ki=(k(n-k))+\frac{k(k+1)}{2} $$ Note that the first sum on the left is just the sum of $k$ copies of $n-k$ and the other sum on the left is just the sum $1+2+\dots+k$. A bit of simplification on the right gives you $$ T(n)=T(n-k)+nk-\frac{k(k-1)}{2} $$ as required.