I have been reading analysis of insertion sort in the "Introduction to algorithms" and faced a problem with understanding a specific summation notation when the worst case occurs.
I know how one can get formula for arithmetic series when we deal with while loop header, I mean 2+3+...+n equals to (n*(n+1) / 2) - 1. But what I do not understand is how one can get formula for while loop body:
It is obvious, that we execute while loop body one time less, than while loop header, because of the final conditional test. Hence, we should subtract one. But how do we get n * (n - 1) / 2?