Can someone explain me this summation?

Solution 1:

The sum counts the triplets $(i,j,k)$ with $0 \leq i < j < k \leq n-1$, hence the 3-element subsets of the $n$-element set $\{0, 1, ..., n-1\}$. The number of such subsets is $\binom{n}{3} = \frac{n^3}{6} - \frac{n^2}{2} + \frac{n}{3}$.

Solution 2:

We can use the identity $$ \sum_{k=m}^n\binom{k}{m}=\binom{n+1}{m+1}\tag{1} $$ three times to get $$ \begin{align} \sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}\sum_{k=j+1}^{n-1}1 &=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\sum_{k=0}^{n-j-2}\binom{k}{0}\tag{2}\\ &=\sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}\binom{n-j-1}{1}\tag{3}\\ &=\sum_{i=0}^{n-1}\sum_{j=0}^{n-i-2}\binom{j}{1}\tag{4}\\ &=\sum_{i=0}^{n-1}\binom{n-i-1}{2}\tag{5}\\ &=\sum_{i=0}^{n-1}\binom{i}{2}\tag{6}\\[3pt] &=\binom{n}{3}\tag{7}\\[6pt] &=\frac{n^3-3n^2+2n}6\tag{8} \end{align} $$ Explanation:
$(2)$: reindex $k\mapsto n-1-k$ and write $1$ as $\binom{k}{0}$
$(3)$: apply $(1)$
$(4)$: reindex $j\mapsto n-1-j$
$(5)$: apply $(1)$
$(6)$: reindex $i\mapsto n-1-i$
$(7)$: apply $(1)$
$(8)$: expand the binomial coefficient

Identity $(1)$ follows from the recursion for Pascal's Triangle and the Telescoping Sum $$ \begin{align} \sum_{k=m}^n\binom{k}{m} &=\sum_{k=m}^n\left[\binom{k+1}{m+1}-\binom{k}{m+1}\right]\\ &=\binom{n+1}{m+1}\tag{9} \end{align} $$

Solution 3:

$$\sum _{i=0}^{n-1}\left(\sum _{j=i+1}^{n-1}\left(\sum _{k=j+1}^{n-1}\:\left(1\right)\right)\:\right)$$

If you want to do it the hard way, just follow the order of operations and compute the inner sums first:

$\sum_{k=j+1}^{n-1} 1=(n-1)-(j+1)+1=n-j-1$ because you are adding 1 that many times.

$\sum_{j=i+1}^{n-1} (n-j-1)=\sum_{j=i+1}^{n-1}n-\sum_{j=i+1}^{n-1} j-\sum_{j=i+1}^{n-1}1=n\cdot(n-i-1)-\left(\dfrac{1}{2}(n-i-1)(n+i)\right)-(n-i-1)=\dfrac{1}{2}(n-i-1)(n-i-2)$

You should be able to find through the same approach that $\sum_{i=0}^{n-1} \dfrac{1}{2}(n-i-1)(n-i-2)=\dfrac{n^3}{6}-\dfrac{n^2}{2}+\dfrac{n}{3}$

Solution 4:

Here is a small supplement with focus on notational convention which might be useful.

\begin{align*} \sum_{i=0}^{n-1}1&=\sum_{0\leq i\leq n-1}1=\binom{n}{1}=n\\ \sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}1&=\sum_{0\leq i<j\leq n-1}1=\binom{n}{2} =\frac{n^2}{2}-\frac{n}{2}\\ \sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}\sum_{k=j+1}^{n-1}1&=\sum_{0\leq i<j<k\leq n-1}1=\binom{n}{3} =\frac{n^3}{6}-\frac{n^2}{2}+\frac{n}{3}\\ \end{align*}

Solution 5:

$$\begin{align} \sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}\sum_{k=j+1}^{n-1}1 &=\sum_{k=2}^{n-1}\sum_{j=1}^{k-1}\sum_{i=0}^{j-1}\binom i0 &&\text{as }0\le i<j<k\le n-1\\ &=\sum_{k=2}^{n-1}\sum_{j=1}^{k-1}\binom j1\\ &=\sum_{k=2}^{n-1}\binom k2\\ &=\binom n3\\ &=\frac {n^3}2-\frac{n^2}2+\frac n3\qquad\blacksquare\end{align}$$