proof that (N–1) + (N–2) + (N–3) + ... + 1= N*(N–1)/2
"I am currently a Software Engineering student at ALX. I'm passionate about technology and enjoy conducting research to find answers on my own. I have a natural inclination to ask 'WHY' more often than 'HOW'.
"While working on projects at ALX, I have acquired a wealth of interesting and diverse knowledge about software engineering and computer science in general. Therefore, I needed a place to store and save all this information, allowing me to refer back to it whenever I forget."
I got this formula from a data structure book in the bubble sort algorithm.
(N-1) + (N-2) +...+ 2 + 1 is a sum of N-1 items. Now reorder the items so, that after the first comes the last, then the second, then the second to last, i.e.(N-1) + 1 + (N-2) + 2 +... The way the items are ordered now you can see that each of those pairs is equal to N ie (N-1+1 is N, N-2+2 is N). Since there are N-1 items, there are (N-1)/2 such pairs. So you're adding N (N-1)/2 times, so the total value is N*(N-1)/2.
Now let me explain with an example
if n = 5
(5 - 1) + (5 - 2) + (5 - 3) + (5 - 4) = 5(5 - 1)/2
4 + 3 + 2 + 1 = 5(4)/2
10 = 10
Now reorder the items so, that after the first comes the last, then the second, then the second to last4 + 1 = 5, 3 + 2 = 5
Since there are N-1 items(5 - 1) + (5 - 2) + (5 - 3) + (5 - 4)
there are (N-1)/2 such pairs (5 - 1)/2 = 2(4 + 1 = 5), (3 + 2 = 5)
So you're adding N (N-1)/2 times
ie add N 2 times5 + 5 = 10
