Sum of arithmetic progressions There is this sum: 
$$\sum_{i=0}^{n-1}\left(\sum_{j=i+1}^{n-1}(n-j-1)\right)=\frac{1}{6}(n-2)(n-1)n$$
I don't understand how the formula is derived. What I do currently understand is this: For each i, starting with 0 and ending with n-1 we have a sum like this: 
$$(n-j_{i+1}-1) + (n-j_{i+2}-1)+...+(n-j_{n-1}-1)$$
All these small sums are of course added in a grand total. For a simple case like n = 5 we have these sums:
Sums computed for n = 5
I think the grand total could be expressed like this:
$$\frac{(n-2)(n-1)}{2} + \frac{(n-3)(n-2)}{2}+...+1$$
but I have no clue how to get from this expression to the formula of the sum. I need a step by step proof of how this formula is derived. I don't have a formal training in math.
 A: I'll provide a 'geometric' picture. The algebraic deriviation follows easily. We convert the sum into a counting of tokens.
The dummy variables $i,j$ ranges over a right traingle with $(n-1)$ tokens on each side. The summand represents the 'height' of the stacks of tokens. We can see that the stack forms a sort of polyhedra. Therefore, to better characterize the sum, we can 'switch' the way we count, by counting horizontal 'slices' rather than 'stacks'. That is, by Abel transformation.
$$\sum_i\sum_{j\ge i+1}(n-j+1)=\sum_i i(i+1)/2$$
It should be easy to go on from here. The sum of squares has a well-known formula.
A: The innermost sum is an arithmetic progression,
$$\sum_{j=i+1}^{n-1}(n-j-1)=\frac12(n-i-1)(n-i-2)\ .$$
Then you have to sum this for $i$ from $0$ to $n-1$.  The most straightforward way is if you know the formulae for $\sum i$ and $\sum i^2$.  Then we have
$$\eqalign{\sum_{i=0}^{n-1}\frac12(n-i-1)(n-i-2)
  &=\frac12\sum_{i=0}^{n-1}[(n-1)(n-2)-(2n-3)i+i^2]\cr
  &=\frac12n(n-1)(n-2)-\frac12(2n-3)\frac12n(n-1)\cr
  &\qquad\qquad\qquad\qquad+\frac12\frac16n(n-1)(2n-1)\cr
  &=\frac1{12}n(n-1)[6(n-2)-3(2n-3)+(2n-1)]\cr
  &=\frac16n(n-1)(n-2)\ .\cr}$$
A: You can sum vertically instead of horizontally!
Refer to the table:
$$\begin{array}{c|c|c}
i/j&1&2&3&\cdots &n-3&n-2&n-1\\
\hline
0&n-2&n-3&n-4&\cdots&2&1&0\\
1&&n-3&n-4&\cdots&2&1&0\\
2&&&n-4&\cdots&2&1&0\\
\vdots&\cdots\\
n-3&&&&\cdots&\cdots&1&0\\
n-2&&&&\cdots&\cdots&\cdots&0\\
n-1&&&&\cdots&\cdots&\cdots&\cdots&
\end{array}\\
\sum_{i=0}^{n-1}\left(\sum_{j=i+1}^{n-1}(n-j-1)\right)=\sum_{i=0}^{n-3}(i+1)(n-i-2)=\\
\sum_{i=1}^{n-2}i(n-i-1)=(n-1)\sum_{i=1}^{n-2}i-\sum_{i=1}^{n-2}i^2=\\
\frac{(n-1)(1+n-2)}{2}\cdot (n-2)-\frac{(n-2)(n-1)(2(n-2)+1)}{6}=\\
\frac{(n-2)(n-1)[3(n-1)-(2n-3)]}{6}=\frac{1}{6}(n-2)(n-1)n\\$$
Note:
$$\sum_{i=1}^n i=\frac{1+n}{2}\cdot n; \ \ \sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}.$$
A: $$\begin{align}
\sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}(n-j-1)&=
\sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}\sum_{k=j+1}^{n-1}1\\
&=\sum_{0\le i<j< k\le n-1}1\\
&=\sum_{k=2}^{n-1}\sum_{j=1}^{k-1}\sum_{i=0}^{j-1}\binom i0\\
&=\sum_{k=2}^{n-1}\sum_{j=1}^{k-1}\binom j1\\
&=\sum_{k=2}^{n-1}\binom {k}2\\
&=\binom {n}3\\
&=\frac 16 (n-2)(n-1)n\end{align}$$
