The funny thing is that, since then, I've looked at that formula several times and can't for the life of me figure out I got from the above formula to the the sum of the range formula. I guess younger me was smarter than current me.
Let's start with a 4x4 square:
OOOO
OOOO
OOOO
OOOO
Divide it into two triangles:
OOOO
OOO O
OO OO
O OOO
Note that one of the triangles has a side of (n-1) and other has a side of n. Now, let's see how many elements has each triangle. As I said, we can use diagonal lines. So the first diagonal has 1 element:
O
We then add the second diagonal, which has 2 elements (I'll use lower caps for the elements that were already present):
oO
O
The third one has 3 elements:
ooO
oO
O
And finally we add the last one:
oooO
ooO
oO
O
It's easy to see how this procedure can be extended to any triangle and to any square (which can be divided in two triangles).
So we can see that:
1) A triangle of side n has sum(1..n) elements.
2) A square of side n can be decomposed into a triangle of side n and another one of side (n-1).
3) Now you can use some basic algebra to determine the value of sum(n): if sum(n-1) + sum(n) = n^2, and sum(n-1) + n = sum(n), then 2·sum(n) = n^2+n, therefore sum(n) = (n^2+n)/2, or if you prefer, sum(n)=n·(n+1)/2.
n^2 = sum(1..n) - sum(1..n-1) = 2sum(1..n-1) + n
=> n^2 - n = 2sum(1..n-1) => n(n-1) = 2*sum(1..n-1) => sum(1..n-1) = n(n-1)/2
And you can rewrite that as... sum(1..n) = n(n+1)/2
This is an awesome visualization, by the way.
Yes. I meant n^2 = sum(1..n-1) + sum(1..n).