Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
    
$\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 ... – Brian M. Scott 7 hours ago
    
... to this question. – Brian M. Scott 7 hours ago
    
@BrianM.Scott Why is it n-i-j? shouldnt it be n-i-j? – ravelinx 7 hours ago
    
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. – Brian M. Scott 7 hours ago

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

share|cite|improve this answer
    
nice and clear! – KonKan 7 hours ago

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

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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