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

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

`(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 youre adding N (N-1)/2 times, so the total value is `N*(N-1)/2`

.

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.

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

Try to make pairs of numbers from the set. The first + the last; the second + the one before last. It means n-1 + 1; n-2 + 2. The result is always n. And since you are adding two numbers together, there are only (n-1)/2 pairs that can be made from (n-1) numbers.

So it is like (N-1)/2 * N.