Tricky Nested Summation I am trying to analyze a programming algorithm that has three nested loops. The algorithm looks like this: $$\sum_{i=0}^{n} \sum_{j=i}^{n}\sum_{k=i}^{j} 1$$.
I am trying to simplify it. These are the steps I have taken so far:
Step 1 $\sum_{i=0}^{n} \sum_{j=i}^{n} (j - i + 1)$
Step 2 $\sum_{i=0}^{n} \sum_{j=i}^{n - i + 1} (j)$
Step 3 $\sum_{i=0}^{n} \frac{(n - i + 1)(n - i + 2)}{2}$
What would I do next?
Thanks
 A: Your second step should have
$$\sum_{i=0}^n\sum_{j=\color{red}1}^{n-i+1}j\;,$$
though judging by your third step, that was just a typo. You can now simplify your third stage. As $i$ runs from $0$ through $n$, $n-i+1$ runs from $n+1$ down through $1$, so we can let $\ell=n-i+1$:
$$\begin{align*}
\sum_{i=0}^n\frac{(n-i+1)(n-i+2)}2&=\frac12\sum_{\ell=1}^{n+1}\ell(\ell+1)\\
&=\frac12\left(\sum_{\ell=1}^{n+1}\ell^2+\sum_{\ell=1}^{n+1}\ell\right)\;.
\end{align*}$$
If you don’t know the formula
$$\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}6\;,$$
this is a good time to learn it; it’s the only remaining tool that you need.
Alternatively, you can notice that you’re really just counting the triples $\langle i,j,k\rangle$ such that 
$$0\le i\le k\le j\le n\;.\tag{1}$$
If we let $k'=k+1$ and $j'=j+2$, we find that $\langle i,j,k\rangle$ satisfies $(1)$ if and only if
$$0\le i<k'<j'\le n+2\;.$$
There are $n+3$ integers in the range $[0,n+2]$, so there are $\binom{n+3}3$ ways to choose $3$ distinct integers $i,j'$, and $k'$ from this range. Once they’ve been chosen, there’s only one way to order them so that $i<k'<j'$, and replacing $k'$ and $j'$ by $k=k'-1$ and $j=j'-2$, respectively, gives us a triple $\langle i,j,k\rangle$ satisfying $(1)$. Thus, your original summation is equal to
$$\binom{n+3}3=\frac16(n+3)(n+2)(n+1)\;.$$
A: $$\begin{align}
\sum_{i=0}^n\sum_{j=i}^n\sum_{k=i}^j 1
&=\sum_{j=0}^n\sum_{k=0}^j\sum_{i=0}^k \binom {i+0}0
&&(0\le i\le k\le j\le n)\\
&=\sum_{j=0}^n\sum_{k=0}^j\binom {k+1}1\\
&=\sum_{j=0}^n\binom {j+2}2\\
&=\binom {n+3}3\qquad\blacksquare
\end{align}$$
A: *

*Multiply $n-i+1\quad$ and $n-i+2\quad$.    

*The result will be a quadratic polynomial in $i\quad$ in the form $a+bi+ci^2\quad$.   

*Your desired result will be $(a·(n+1)+b·(n^2+n)/2+c·(2·n^3+3·n^2+n)/6)/2\quad$.

A: For a first approximation,
approximate the sums
by integrals:
$\begin{array}\\
\sum_{i=0}^{n} \sum_{j=i}^{n}\sum_{k=i}^{j} 1
&\approx \int_{0}^{n} dx \int_{x}^{n} dy\int_{x}^{y} dz\\
&=\int_{0}^{n} dx \int_{x}^{n}(y-x) dy\\
&=\int_{0}^{n} dx (\frac{y^2}{2}-xy)|_{x}^{n}\\
&=\int_{0}^{n} dx (\frac{n^2-x^2}{2}-x(n-x))\\
&=\int_{0}^{n} dx (\frac{n^2+x^2}{2}-xn)\\
&= (\frac{xn^2}{2}+\frac{x^3}{6}-\frac{x^2n}{2})|_{0}^{n}\\
&= (\frac{n^3}{2}+\frac{n^3}{6}-\frac{n^3}{2})\\
&= \frac{n^3}{6}\\
\end{array}
$
For many usages,
this is good enough.
A: In this answer, it is shown that
$$
\sum_{j=k}^n\binom{j}{k}=\binom{n+1}{k+1}\tag{1}
$$
We can apply $(1)$ twice to get
$$
\begin{align}
\sum_{i=0}^n\sum_{j=i}^n\sum_{k=i}^j1
&=\sum_{i=0}^n\sum_{j=i}^n\binom{j-i+1}{1}\tag{2}\\
&=\sum_{i=0}^n\sum_{j=1}^{n-i+1}\binom{j}{1}\tag{3}\\
&=\sum_{i=0}^n\binom{n-i+2}{2}\tag{4}\\
&=\sum_{i=2}^{n+2}\binom{i}{2}\tag{5}\\[3pt]
&=\binom{n+3}{3}\tag{6}
\end{align}
$$
Explanation:
$(2)$: write the sum as a binomial coefficient
$(3)$: $j\mapsto j+i-1$
$(4)$: apply $(1)$
$(5)$: $i\mapsto n+2-i$
$(6)$: apply $(1)$
