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