Getting a closed form from $\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \sum_{k=1}^{j} 1$

Question

I need to get a closed form from

$$ \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \sum_{k=1}^{j} 1 $$

Starting from the most outer summation, I got

$$ \sum_{k=1}^{j} 1 = j $$

But now I don't know how to proceed with:

$$ \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} j $$

Could you guys please help me?

Thanks in advance.

Answer 1

Thanks @Winther for pointing out the previous mistake

\begin{equation} \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \sum_{k=1}^{j} 1 \end{equation} We know that \begin{equation} \sum_{k=1}^{j} 1 = j \end{equation} So \begin{equation} \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \sum_{k=1}^{j} 1 = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} j \end{equation} \begin{equation} \sum_{j=i+1}^{n} j = \sum_{j=1}^{n} j - \sum_{j=1}^{i} j = \frac{n(n+1)}{2} - \frac{i(i+1)}{2} \end{equation} \begin{equation} \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \sum_{k=1}^{j} 1 = \sum_{i=1}^{n-1} ( \frac{n(n+1)}{2} - \frac{i(i+1)}{2}) = \frac{n(n+1)(n-1)}{2} - \frac{1}{2} \sum_{i=1}^{n-1} i+i^2 \end{equation} But \begin{align} \sum_{i=1}^{n-1} i &= \frac{(n-1)n}{2} \\ \sum_{i=1}^{n-1} i^2 &= \frac{(n-1)n(2n-1)}{6} \end{align} So \begin{equation} \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \sum_{k=1}^{j} 1 = \frac{n(n+1)(n-1)}{2} - \frac{1}{2} (\frac{(n-1)n}{2} + \frac{(n-1)n(2n-1)}{6}) \end{equation} Let's arrange \begin{equation} \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \sum_{k=1}^{j} 1 = \frac{6n(n+1)(n-1) - 3n(n-1) - n(n-1)(2n-1)}{12} \end{equation}

We arrive at the most compact form, \begin{equation} \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \sum_{k=1}^{j} 1 = \frac{(n-1)n(6n + 6 - 3 - 2n + 1)}{12} = \frac{(n-1)n(n + 1)}{3} \end{equation}

Answer 2

Knowing that \begin{align} \sum_{k=1}^{n} (1) &= n \\ \sum_{k=1}^{n} k &= \frac{n \, (n+1)}{2} \\ \sum_{k=1}^{n} k^2 &= \frac{n(n+1)(2n+1)}{6} \end{align} then \begin{align} S &= \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \sum_{k=1}^{j} (1) \\ &= \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} j \\ &= \sum_{i=1}^{n-1} \left(\sum_{j=1}^{n} j - \sum_{j=1}^{i} i \right) \\ &= \sum_{i=1}^{n-1} \left(\binom{n}{2} - \frac{i(i+1)}{2}\right) \\ &= \binom{n}{2} \, \sum_{i=1}^{n-1} (1) - \frac{1}{2} \, \sum_{i=1}^{n-1} i^2 - \frac{1}{2} \, \sum_{i=1}^{n-1} i \\ &= \binom{n}{2} \, (n-1) - \frac{n(n-1)}{4} - \frac{n(n-1)(2n-1)}{12} \\ &= \frac{(n-1)(n)(n+1)}{3} = 2 \, \binom{n+1}{3}. \end{align}

Answer 3

$$ \begin{align} \sum_{i=1}^{n-1}\sum_{j=i+1}^n\sum_{k=1}^j1 &=\sum_{i=1}^{n-1}\sum_{j=1}^{n-i}\sum_{k=1}^{j+i}1\tag1\\ &=\sum_{i=1}^{n-1}\sum_{j=1}^{n-i}(j+i)\tag2\\ &=\sum_{i=1}^{n-1}\binom{n-i+1}2+i(n-i)\tag3\\ &=\sum_{i=1}^{n-1}\binom{i+1}2+i(n-i)\tag4\\ &=\sum_{i=1}^{n-1}\left[n\binom{i}{1}-\binom{i}{2}\right]\tag5\\[3pt] &=n\binom{n}{2}-\binom{n}{3}\tag6\\[6pt] &=(n+1)\binom{n}{2}-\binom{n+1}{3}\tag7\\[3pt] &=3\binom{n+1}{3}-\binom{n+1}{3}\tag8\\[6pt] &=2\binom{n+1}{3}\tag9 \end{align} $$ Explanation:
$(1)$: substitute $j\mapsto j+i$
$(2)$: evaluate the inner sum
$(3)$: evaluate the inner sum
$(4)$: substitute $i\mapsto n-i$
$(5)$: recombine terms
$(6)$: sum the binomial coefficients
$(7)$: add $\binom{n}{2}$ to both terms of the difference
$(8)$: $\frac{n+1}3\binom{n}{2}=\binom{n+1}{3}$
$(9)$: evaluate the difference

Answer 4

Sum by sum: $$\begin{align}\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \sum_{k=1}^{j} 1&=\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} j=\\ &=\sum_{i=1}^{n-1} \frac{i+1+n}{2}\cdot (n-i-1+1)=\\ &=\frac12 \sum_{i=1}^{n-1} n^2+n-i^2-i=\\ &=\frac12\left[(n^2+n)(n-1)-\frac{(n-1)n(2(n-1)+1)}{6}-\frac{(n-1)n}{2}\right]=\\ &=\frac12n(n-1)\left[n+1-\frac{2n-1}{3}-1\right]=\\ &=\frac12n(n-1)\cdot \frac{n+1}{3}.\end{align}$$