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

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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