parametrization of the result of $\sum_{i=1}^{N-2}\sum_{j=i+1}^{N-1}\sum_{k=j+1}^N$ as a function of $N$

Question

As stated in the title, what's the result as a function of N for

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

Answer 1

Summing from $a$ to $b$ where $b\geqslant a-1$ has $b-a+1$ summands

$$\sum_a^b 1 = \underbrace{1+1+\cdots 1}_{\textstyle b-a+1 \text{ times}} \tag0$$ where the empty sum equals $0$ by definition. Hence

$$\begin{align} \sum_{i=1}^{N-2}\sum_{j=i+1}^{N-1}\sum_{k=j+1}^N 1 &= \sum_{i=1}^{N-2}\sum_{j=i+1}^{N-1} (N-j)\\ &= \sum_{i=1}^{N-2}\left(N\sum_{j=i+1}^{N-1}1 - \sum_{j=i+1}^{N-1}j\right)\\ &\stackrel{(1)}= \sum_{i=1}^{N-2}\left(N(N-1-i) - \frac N2(N-1) + \frac{i}2(i+1)) \right)\\ &= \frac12 \sum_{i=1}^{N-2}\left(N^2-N +i(1-2N) +i^2 \right)\\ &=: \frac12(A+B+C) \end{align}$$

The last summand can be divided into tree parts $A$, $B$ and $C$:

• $A$ not depending on the summation index $i$,
• $B$ depending (linearly) on $i$ and
• $C$ depending (linearly) on $i^2$, see here

The first one is computaed using $(0)$ again: $$A= (N-2)(N^2-N) = N(N-1)(N-2)$$

The second one uses

$$\sum_{k=1}^n k= \frac n2(n+1) \tag 1$$

and the third one uses

$$\sum_{k=1}^n k^2= \frac n6(n+1)(2n+1) \tag 2$$

$$\begin{align} B &= (1-2N)\sum_{i=1}^{N-2}i \stackrel{(1)}= \frac12(1-2N)(N-1)(N-2) \\ C &\stackrel{(2)}= \sum_{i=1}^{N-2}i^2 = \frac16(N-1)(N-2)(2N-3) \\ B+C &= -\frac23 N(N-1)(N-2)\\ \sum = \frac12(A+B+C) &= \frac16 N(N-1)(N-2)\\ \end{align}$$

which are the Tetrahedral Numbers.

Answer 2

We obtain \begin{align*} \sum_{i=1}^{N-2}&\sum_{j=i+1}^{N-1}\sum_{k=j+1}^N1 =\sum_{\color{blue}{1\leq i<j<k\leq N}}1=\binom{N}{3} \end{align*}

In the middle sum we write the index region somewhat more conveniently. This way we see we count the number of ordered triples in $\{(i,j,k)\in\mathbb{N}^3|1\leq i<j<k\leq N\}$ which is the number of combinations of three elements in the set $[N]=\{1,2,\ldots,N\}$.