Sum of arithmetic progressions

Question

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.

Answer 1

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}$$

Answer 2

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.

Answer 3

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

Answer 4

$$\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}$$