Closed Form For $n$ Consecutive Summations

Question

If $\xi, a, b, c, \dots, \mu, n \in \mathbb{Z}$

Is there a closed form of the following concesutive $n$-summations?

$$S = \sum_{a=0}^{\xi-1} \sum_{b=0}^{a-1} \sum_{c=0}^{b-1} \cdots \sum_{n=0}^{\mu-1} a + b + c + \cdots + n$$

Answer 1

HINT: $$\begin{align}S &= \sum_{a=0}^{ξ-1} \sum_{b=0}^{a-1} \sum_{c=0}^{b-1}\cdots\sum_{n=0}^{μ-1} (a + b + c +\cdots+n)\\&=\sum_{a=0}^{ξ-1} \sum_{b=0}^{a-1} \sum_{c=0}^{b-1}\cdots \left(n(a + b + c + \cdots)+\sum_{n=0}^{μ-1} n\right)\\&=\quad...\end{align}$$ So whenever a variable is different to that for the sum (e.g. $n=0$, and say $c$ was your variable) then just multiply it by $n$ to give $nc$. If it is not, use that identity that $$\sum_{i=1}^k=\frac12k(k+1)$$ and repeat this for each summation.

Answer 2

For the sum in its current form, it is hard to tell how many levels of summation are there.

We will let $p$ be the level of summations and relabel the summation indices from $a, b, c, \cdots, n$ to $a_p, a_{p-1}, \ldots, a_1$.

• For any $m \in \mathbb{Z}_{+}$, let $[m]$ be the set $\{ 0, 1, \cdots, m-1 \}$ with $m$ elements.
• For any finite set $X$, and $m \in \mathbb{Z}_{+}$, let $\mathcal{D}_m(X) = \{ (x_1,\ldots,x_m ) \in X^m : x_i \text{ distinct } \}$ be the ordered $m$-tuples from $X$ with distinct entries.

It is easy to see $\mathcal{D}_m(X)$ contains $\displaystyle\;|\mathcal{D}_m(X)| = m! \binom{|X|}{m}$ elements.

It terms of these, the expression we have can be evaluated as

$$\begin{align} & \sum_{a_p=0}^{\xi - 1}\sum_{a_{p-1}=0}^{a_p-1}\cdots \sum_{a_1=0}^{a_2-1} (a_1 + \cdots a_p)\\ &\quad\quad = \sum_{0\le a_1 < a_2 < \cdots < a_p < \xi}(a_1 + \cdots + a_p) = \frac{1}{p!}\sum_{(a_1,\ldots,a_p) \in \mathcal{D}_p([\xi])} (a_1 + \cdots + a_p)\\ &\quad\quad = \frac{1}{(p-1)!}\sum_{(a_1,\ldots,a_p) \in \mathcal{D}_p([\xi])} a_p = \frac{1}{(p-1)!}\sum_{a=0}^{\xi - 1} \sum_{(a_1,\ldots,a_{p-1}) \in \mathcal{D}_{p-1}([\xi] \setminus \{ a \})} a\\ &\quad\quad = \frac{1}{(p-1)!}\sum_{a=0}^{\xi-1}a \left|\mathcal{D}_{p-1}([\xi] \setminus \{ a \})\right|\\ &\quad\quad = \frac{\xi(\xi-1)}{2} \binom{\xi-1}{p-1} \end{align} $$

Answer 3

Consider easier cases: $$\sum_{x_1=0}^{y-1}\sum_{x_2=0}{x_1-1}(x_1+x_2)=\sum_{x_1=0}^{y-1}\left(x_1^2+\frac{(x_1-1)x_1}{2}\right)=\\ \sum_{x_1=0}^{y-1}\left(\frac32x_1^2-\frac12x_1\right)=\cdots$$ $$\sum_{x_1=0}^{y-1}\sum_{x_2=0}^{x_1-1}\sum_{x_3=0}^{x_2-1}(x_1+x_2+x_3)=\sum_{x_1=0}^{y-1}\sum_{x_2=0}^{x_1-1} \left(x_1x_2+x_2+\frac{(x_1-1)x_2}{2}\right)=\cdots=\sum_{x_1=0}^{y-1}\left(x_1^3-\frac32x_1^2+\frac12x_1\right)=\cdots$$