formulaproof

What is the proof of of (N–1) + (N–2) + (N–3) + ... + 1= N*(N–1)/2


I got this formula from a data structure book in the bubble sort algorithm.

I know that we are (n-1) * (n times), but why the division by 2?

Can anyone please explain this to me or give the detailed proof for it.

Thank you


Solution

  • See triangle numbers.