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.

Thanks in advance


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

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

  • 2
    $\begingroup$ beautiful and simple. $\endgroup$ – 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}$$


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.