6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ $\sum_{k=j+1}^{n-1}1$ is the sum of $n-1-j$ terms, each of which is $1$, so it’s simply equal to $n-1-j$, and your summation reduces to $$\sum_{k=0}^{n-1}\sum_{j=i+1}^{n-1}(n-1-j)\;.$$ Now work on the inner summation, $$\sum_{j=i+1}^{n-1}(n-1-j) =\sum_{j=i+1}^{n-1}(n-1)-\sum_{j=i+1}^{n-1} j\;.$$ The first summation on the right is just the some of copies of $n-1$, so it’s easy to evaluate. The second summation on the right is the sum of consecutive integers; techniques for dealing with it, as well as some other useful facts, are mentioned in my answer ... $\endgroup$ – Brian M. Scott Apr 3 '16 at 1:35
  • 1
    $\begingroup$ ... to this question. $\endgroup$ – Brian M. Scott Apr 3 '16 at 1:35
  • $\begingroup$ @BrianM.Scott Why is it n-i-j? shouldnt it be n-i-j? $\endgroup$ – ravelinx Apr 3 '16 at 1:38
  • $\begingroup$ There are $n-1$ integers from $1$ through $n-1$. If we start $j$ at $i+1$, we’re throwing away the first $i$ of them, from $1$ through $i$. That leaves $(n-1)-i$ integers for $j$ to run through. $\endgroup$ – Brian M. Scott Apr 3 '16 at 1:40
14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ nice and clear! $\endgroup$ – KonKan Apr 3 '16 at 1:48
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.