Is there a closed-form expression for this nested sum?

$$s(n)=\sum_{i=1}^n\;\; \sum_{j=i+1}^n \sum_{k=i+j-1}^n1$$

If yes, what is it and how can it be derived?

  • $\begingroup$ Shouldn't that be a $k$ in the last sum, instead of the $1$? $\endgroup$ – Bobson Dugnutt Feb 21 '16 at 10:33
  • $\begingroup$ Did you try just computing it? Where does the problem lie exactly? $\endgroup$ – user258700 Feb 21 '16 at 10:34
  • $\begingroup$ @Lovsovs it's actually a constant that comes out. Hence I put 1. $\endgroup$ – igor Feb 21 '16 at 10:43
  • 1
    $\begingroup$ Actually turns out that $\frac{n(n-1)}{2}$ is not correct answer, even though Maple and naive derivation suggests that. This formula does not work for $n>3$ correctly. $\endgroup$ – Sil Feb 21 '16 at 15:06
  • 2
    $\begingroup$ Interesting question... deceptively simple looking but not quite so! (+1) $\endgroup$ – hypergeometric Feb 21 '16 at 15:10

The usual convention with the sum sign $\sum$ is that $\sum_{k=p}^q a_k:=0$ if $q<p$. This has the following effect: Given an $i$ with $1\leq i\leq n$ the next index variable $j$ has to satisfy $$i+1\leq j\leq\min\{n, n+1-i\}=n+1-i\ .$$ This then implies that the variable $i$ in fact has to satisfy $2i\leq n$, or $$1\leq i\leq\left\lfloor{n\over2}\right\rfloor\ .$$ Given $i$ and $j$ with these constraints the innermost sum becomes $$\sum_{k=i+j-1}^n 1=n+2-i-j\ .$$ The next sum (over $j$) then becomes $$A_i:=\sum_{j=i+1}^{n+1-i}(n+2-i-j)$$ and has $n+1-2i$ terms. It follows that $$A_i=(n+1-2i)\>{1\over2}\>(n+2-2i)\qquad\bigl(1\leq i\leq\lfloor n/2\rfloor\bigr)\ .$$ Here we have used that the sum of a finite arithmetic series is the number of terms times the arithmetic mean of its outermost terms. From now on we have to distinguish the cases of even and odd $n$.

If $n=2m$ then Mathematica produces $$s(n)=\sum_{i=1}^m A_i={4m^3+3m^2-m\over6}={n(2n^2+3n-2)\over 24}\ .$$ If $n=2m+1$ we similarly obtain $$s(n)=\sum_{i=1}^m A_i={4m^3+9m^2+5m\over6}={2n^3+3n^2-2n-3\over 24}\ .$$


By choosing experimentally a small value of $n$ and writing out by hand in a simple $i-j$ grid the values of the innermost summation, it becomes clear that:

  • If $n=2m$:

$$\begin{align}S(n)=S(2m)&=\sum_{s=1}^m \sum_{r=1}^{2s-1}r=\sum_{s=1}^m\binom {2s}2\\ &=\frac 16m(m+1)(4m-1)\end{align}$$

  • If $n=2m+1$:

$$\begin{align}S(n)=S(2m+1)&=\sum_{s=1}^m \sum_{r=1}^{2s}r=\sum_{s=1}^m\binom {2s+1}2\\ &=\frac 16m(m+1)(4m+5)\end{align}$$

The above can also be derived as follows:

By considering each $i,j$ combination in turn and the corresponding limits on $k$ (or as pointed out by Christian Blatter in his solution), it is clear that the applicable limits of $i,j$ are narrower $\color{red}{\text{(shown below in red})}$ than in the original question, as the innermost summation cannot be negative, as specified by the condition in the Iverson brackets $\color{lightblue}{\text{(shown below in light blue)}}$.

  • If $n=2m$: $$\begin{align} \sum_{i=1}^n\;\;\sum_{j=i+1}^n\sum_{k=i+j-1}^n1 &=\sum_{i=1}^{n}\sum_{j=i+1}^{n}(n-i-j+2)\color{lightblue}{[n-i-j+2\ge0]}\\ &=\sum_{i=1}^{2m}\sum_{j=i+1}^{2m}(2m-i-j+2)\color{lightblue}{[2m-i-j+2\ge0]} &&\text{putting }n=2m\\ &=\sum_{i=1}^\color{red}m\sum_{j=i+1}^{\color{red}{2m-i+1}}(2m-i-j+2) &&\text{using applicable limits}\\ &=\sum_{i=1}^m\sum_{r=1}^{2(m-i+1)-1}r && \text{putting }2m-i-j+2=r\\ &=\sum_{s=1}^m\sum_{r=1}^{2s-1}r\end{align}$$

The case for $n=2m+1$ can be shown using a similar method.


Hint: the general solution strategy is to solve first the innermost sum, expand that, and repeat the procedure.

For solving the sums use

$\sum_{k=1}^n k = (n(n+1))/2$,

$\sum_{k=1}^n k^2 = (n(n+1)(2n+1))/6$,

$\sum_{k=1}^n k^3 = (n^2(n+1)^2)/4$.

  • 3
    $\begingroup$ The most inner sum depends on the value of $i$ and $j$ from the outer sums. This makes it a bit tricky. $\endgroup$ – igor Feb 21 '16 at 11:00
  • $\begingroup$ I wouldn't call this tricky, these are only algebraic "high school" manipulations. $\endgroup$ – andre Feb 21 '16 at 11:36
  • $\begingroup$ @hypergeometric, ahem, so you are telling me that a case differentiation is not high school stuff? o.k.? $\endgroup$ – andre Feb 22 '16 at 18:44

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.