How to compute for the time complexity of this triple nested loop

Question

for (i=1 to n-1) {
  for (j=i+1 to n) {
    for (k=1 to j) {
    }
  }
}

The Answer is: $$\frac{n^3}{3} - \frac{n}{3}$$

I'm trying to use summation to solve for it, but I'm having a bit of trouble:

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

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

$$\sum_i^{n-1}(i+1)+(i+2)+...(i+1+n)j$$

Stuck here

Answer 1

Using $$\sum_{k=1}^{N}k=\frac{N(N+1)}{2}$$ and $$i(i+1)=\frac 13((i+2)(i+1)i-(i+1)i(i-1)),$$ we have

$$\begin{align}\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}j\right)\\&=\sum_{i=1}^{n-1}\left(\frac{n(n+1)}{2}-\frac{i(i+1)}{2}\right)\\&=\frac{n(n+1)}{2}(n-1)-\frac 12\cdot\frac 13\sum_{i=1}^{n-1}\left((i+2)(i+1)i-(i+1)i(i-1)\right)\\&=\frac{(n+1)n(n-1)}{2}-\frac 16(n+1)n(n-1)\\&=\frac{(n+1)n(n-1)}{3}\end{align}$$

Answer 2

Here's a less algebraic proof .

The sum adds an $1$ for each triple $(i,j,k)$ such that $1 \leq i<j\leq n$ and $1 \leq k \leq j \leq n$ . First choose a $j$ from $1$ to $n$ . For each such $j$ there are $j-1$ choices for $i$ and $j$ choices for $k$ . So the sum is equivalent with :

$$\sum_{j=1}^{n}j(j-1)=\sum_{j=1}^{n} j^2-\sum_{j=1}^{n} j=\frac{n(n+1)(2n+1)}{6}-\frac{n(n+1)}{2}=\frac{n(n+1)(2n-2)}{6}=\frac{n(n+1)(n-1)}{3}=\frac{n^3-n}{3}$$ as wanted .

Answer 3

$$\begin{align} \color{darkblue}{\sum_{i=1}^{n-1}\sum_{j=i+1}^n}\color{green}{\sum_{k=1}^j 1} &=\color{darkblue}{\sum_{1\le i < j\le n}}\color{green}j\\ &=\color{darkblue}{\sum_{j=2}^n\sum_{i=1}^{j-1}}\color{green}j\\ &=\sum_{j=2}^n j(j-1)\\ &=2\sum_{j=2}^n \binom j2\\ &=2\binom {n+1}3\\ &=\frac {n(n^2-1)}3 &=\frac {n^3}3-\frac n3\qquad\blacksquare \end{align}$$