What is the proof of of (N–1) + (N–2) + (N–3) + …

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 10 years ago.

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

Answer 1

Start with the triangle...

    *
   **
  ***
 ****

representing 1+2+3+4 so far. Cut the triangle in half along one dimension...

     *
    **
  * **
 ** **

Rotate the smaller part 180 degrees, and stick it on top of the bigger part...

    **
    * 

     *
    **
    **
    **

Close the gap to get a rectangle.

At first sight this only works if the base of the rectangle has an even length - but if it has an odd length, you just cut the middle column in half - it still works with a half-unit-wide twice-as-tall (still integer area) strip on one side of your rectangle.

Whatever the base of the triangle, the width of your rectangle is (base / 2) and the height is (base + 1), giving ((base + 1) * base) / 2.

However, my base is your n-1, since the bubble sort compares a pair of items at a time, and therefore iterates over only (n-1) positions for the first loop.

Answer 2

Here's a proof by induction, considering N terms, but it's the same for N - 1:

For N = 0 the formula is obviously true.

Suppose 1 + 2 + 3 + ... + N = N(N + 1) / 2 is true for some natural N.

We'll prove 1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) / 2 is also true by using our previous assumption:

1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1) / 2) + (N + 1) = (N + 1)((N / 2) + 1) = (N + 1)(N + 2) / 2.

So the formula holds for all N.

Answer 3

See triangle numbers.

Answer 4

This is a pretty common proof. One way to prove this is to use mathematical induction. Here is a link: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html

Answer 5

(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 (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.

Answer 6

Sum of arithmetical progression

(A1+AN)/2*N = (1 + (N-1))/2*(N-1) = N*(N-1)/2