# How to simplify this triple summation

I am trying to calculate the following summation by n :

\begin{align} \sum_{i=1}^n \sum_{j=i}^n \sum_{k=i}^j 1 &= \sum_{i=1}^n \sum_{j=i}^n (j-i+1) \\ &= \sum_{i=1}^n \left( \sum_{j=i}^n j - i \sum_{j=i}^n 1 + \sum_{j=i}^n1 \right) \\ &= \sum_{i=1}^n \left( \sum_{j=i}^n j -i(n-i+1)+ (n-i+1)\right) \end{align}

I don't know what to do from there.

$$\begin{eqnarray*}\sum_{i=1}^{n}\sum_{j=i}^{n}(j-i+1)&=&\sum_{i=1}^{n}\sum_{j=0}^{n-i}(n-i-j+1)\\&=&\sum_{i=1}^{n}\binom{n-i+2}{2}\\&=&\sum_{i=2}^{n+1}\binom{i}{2}\\&=&\binom{n+2}{3}=\frac{n(n+1)(n+2)}{6}\end{eqnarray*}$$ by a well-known identity.

• My book gives me this final answer = (n3 +3n2 +2n) / 6 – AlexB Sep 3 '15 at 14:39
• @AlexB: then, probably, your book defines $\sum_{k=i}^{j}1$ for $i>j$ in a different way. – Jack D'Aurizio Sep 3 '15 at 14:45
• The second summation starts at $j=i$ and not $j=1$ and the result in the book is correct. – Claude Leibovici Sep 3 '15 at 14:56
• @AlexB: sorry, I misread an index. Now fixed. – Jack D'Aurizio Sep 3 '15 at 15:06
• I now understand the power of the Iverson bracket. – Akiva Weinberger Sep 4 '15 at 1:59

Using the Iverson bracket, we see that: $$\sum_{x=a}^b f(x)=\sum_x f(x)[a\le x\le b]$$ where $x$ ranges over all integers on the RHS. Another feature of the Iverson bracket is, for any statements $P$ and $Q$, we have $[P\text{ and }Q]=[P][Q]$. This can be used to simplify complicated sums in which the ranges of the summation signs depend on each other.

Using the Iverson bracket, we see your sum is: $$\sum_{i,j,k}[1\le i\le k\le j\le n]$$ Noting that $a\le b$ is the same as $a<b+1$, when working with the integers, we see that the sum is the same as: $$\sum_{i,j,k}[1\le i<k+1<j+2\le n+2]$$ In other words, we want to find the number of ways of choosing three distinct numbers ($i$, $k+1$, and $j+2$) from the set $\{1,2,\dots,n+2\}$. In other words, we're choosing three objects out of $n+2$ objects. This is: $$\binom{n+2}3$$

• beautiful and simple. – user98186 Dec 28 '15 at 21:50

\begin{align} \sum_{i=1}^n \sum_{j=i}^n \sum_{k=i}^j 1 &=\sum_{j=1}^n\sum_{k=1}^j\sum_{k=1}^k1 &&(1\le i\le k\le j\le n)\\ &= \sum_{j=1}^n\sum_{k=1}^j\binom k1\\ &=\sum_{j=1}^n\binom {j+1}2\\ &=\color{red}{\binom {n+2}3} \end{align}