You can arrive to the formula n^2 = sum(1..n) + sum(1..n-1) visually, separating a square into two triangles and fill them adding diagonals. Ok, that doesn't sound very informative, so let me show you an example.

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.

That is an outstanding explanation of the intuition behind that formula, and in ASCII no less! :)

That's a neat visualisation.

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

That's it! Makes me realize how rusty at math I've gotten. :/

Isn't sum(1...n) - sum(1...n-1) just n? (1+2+3+4+5 - (1+2+3+4) = 5). That should be a +, right?

This is an awesome visualization, by the way.

> Isn't sum(1...n) - sum(1...n-1) just n?

Yes. I meant n^2 = sum(1..n-1) + sum(1..n).