Evaluate the triple sum $\sum_{i=0}^{n-1}\sum_{j=i}^{n-1}\sum_{k=i}^{j} 1$

Question

I have trouble evaluating this triple sum , so far I tried this : $$\sum_{i=0}^{n-1}\sum_{j=i}^{n-1}\sum_{k=i}^{j} 1 = \sum_{i=0}^{n-1}\sum_{j=i}^{n-1}(\sum_{k=i}^{j} 1) $$ $$ = \sum_{i=0}^{n-1}\sum_{j=i}^{n-1}(j-i+1)$$ $$ = \sum_{i=0}^{n-1}\sum_{j=i}^{n-1}j \space - \sum_{i=0}^{n-1}\sum_{j=i}^{n-1} i \space + \sum_{i=0}^{n-1}\sum_{j=i}^{n-1}1$$ $$ = \sum_{i=0}^{n-1}(\sum_{j=i}^{n-1}j) \space - \sum_{i=0}^{n-1}(\sum_{j=i}^{n-1} i) \space + \sum_{i=0}^{n-1}(\sum_{j=i}^{n-1}1)$$ $$ = \sum_{i=0}^{n-1}(\frac{(n-i)(n+i-1)}{2})-\space \sum_{i=0}^{n-1}((n-i)i)+\sum_{i=0}^{n-1}(n-i)$$ $$ =\frac{1}{2}\sum_{i=0}^{n-1}(n^2-i^2-n+i)-\sum_{i=0}^{n-1}ni+\sum_{i=0}^{n-1}i^2+\sum_{i=0}^{n-1}n-\sum_{i=0}^{n-1}i $$ $$ =\frac{1}{2}\sum_{i=0}^{n-1}n^2-\frac{1}{2}\sum_{i=0}^{n-1}i^2-\frac{1}{2}\sum_{i=0}^{n-1}n+\frac{1}{2}\sum_{i=0}^{n-1}i-\sum_{i=0}^{n-1}ni+\sum_{i=0}^{n-1}i^2+\sum_{i=0}^{n-1}n-\sum_{i=0}^{n-1}i $$ $$ =\frac{1}{2}\sum_{i=0}^{n-1}n^2+(1-\frac{1}{2})\sum_{i=0}^{n-1}i^2+(1-\frac{1}{2})\sum_{i=0}^{n-1}n+(\frac{1}{2}-n-1)\sum_{i=0}^{n-1}i $$ $$ =\frac{1}{2}\sum_{i=0}^{n-1}n^2+\frac{1}{2}\sum_{i=0}^{n-1}i^2+\frac{1}{2}\sum_{i=0}^{n-1}n-(\frac{2n+1}{2})\sum_{i=0}^{n-1}i $$ $$ =\frac{n^3}{2}+\frac{1}{2}\frac{n(n-1)(2n-1)}{6}+\frac{n^2}{2}-(\frac{2n+1}{2})\frac{n(n-1)}{2}=\frac{n(n^2+3n^2+2)}{6}=\frac{n(n+1)(n+2)}{6}=\binom{n-1+3}{3} $$ But Mathematica yields $\frac{1}{6}n(2+3n+n^2)$. My question is where is my mistake ? $$Edit:$$ I corrected the initial mistake but I still fail to obtain the correct solution. $$ Second Edit:$$ I corrected the second mistake and finally obtained the correct solution.

Answer 1

There's a mistake right up in your first line. You've written

$$ \sum_{k=i}^{j} 1=j+i-1 $$

but this should be

$$ \sum_{k=i}^{j} 1=j-i+1 $$

Edit: second mistake

Between your final two lines you have written that

$$ \sum^{n-1}_{i=0} i = \frac{n(n+1)}{2} $$

which should be

$$ \sum^{n-1}_{i=0} i = \frac{n(n-1)}{2} .$$

This correction should lead to the correct answer.