Can someone explain me this summation? So I need to solve this summation $$\sum _{i=0}^{n-1}\left(\sum _{j=i+1}^{n-1}\left(\sum _{k=j+1}^{n-1}\:\left(1\right)\right)\:\right)$$
and this I know that the answer is $$\frac{n^3}{6}-\frac{n^2}{2}+\frac{n}{3}$$
but how can I arrive to this answer, can someone explain me? thanks
 A: 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}
$$
A: $$\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}$
A: 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*}

A: 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}$.
A: $$\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}$$
