Nested summation - intuition

Question

To begin with, I noted that

$$ \begin{aligned} \displaystyle \sum_{r_1 = 1}^{r} r_1 &= \dfrac{1}{2} r (r+1) \quad &(1)\\ \displaystyle \sum_{r_2 = 1}^{r} \displaystyle \sum_{r_1 = 1}^{r_2} r_1 &= \dfrac{1}{6} r (r+1) (r+2). & \qquad(2) \end{aligned}$$ This led me to suggest the more general conjecture that $$ \begin{aligned} \displaystyle \sum_{r_n = 1}^{r} \displaystyle \sum_{r_{n-1} = 1}^{r_n} \cdots \displaystyle \sum_{r_2 = 1}^{r_3} \displaystyle \sum_{r_1 = 1}^{r_2} r_1 &= \dfrac{1}{(n+1)!} \prod_{k=0}^{n} (r+k) \\ &= \dfrac{1}{(n+1)!} \dfrac{(r+n)!}{(r-1)!} \qquad(\star) \end{aligned} $$

I believe that I've managed to successfully prove this using induction, but on the whole the process isn't very enlightening and given how "nice" the result is I'm led to believe that there's some more general insight here that I'm missing.

I've seen a link to the geometric interpretation of $ (1) $ by "pasting together" two copies of the sum to form a rectangle and I imagine the proof carries through analogously for $ (2) $ by forming a cuboid using 6 copies of the summation, but I'm not sure how to formalise this method of thinking (or indeed how to generalise it to higher dimensions). Of course this is just one particular thought I've had so any alternative proofs would also be welcome!

Answer 1

The essence is already encoded in the indices of the sums.

We can write for positive integer $r$ the sums as \begin{align*} \sum_{r_n=1}^r\sum_{r_{n-1}=1}^{r_n}\cdots\sum_{r_1=1}^{r_2}r_1\tag{1} &=\sum_{r_n=1}^r\sum_{r_{n-1}=1}^{r_n}\cdots\sum_{r_1=1}^{r_2}\sum_{r_0=1}^{r_1}1\\ &=\sum_{\color{blue}{1\leq r_0\leq r_1\leq \cdots\leq r_n\leq r}} 1\tag{2} \end{align*}

The number of summands given by the index range $$1\leq r_0\leq r_1\leq \cdots\leq r_n\leq r$$ is the number of ordered $(n+1)$-tupel $(r_0,\ldots,r_n)$ between $1$ and $r$ with repetition. This number is given by the binomial coefficient \begin{align*} \binom{(n+1)+r-1}{n+1}=\binom{n+r}{n+1} \end{align*} which corresponds to ($\star$) in OP's post.

Answer 2

These numbers are called Simplicial polytopic numbers.

$(1)$ corresponds to triangular numbers, $(2)$ to tetrahedral numbers, and so on. The relation with binomial coefficients and in fact to the whole Pascal triangle is well known.

Answer 3

We start off with a basic identity which can be proven combinatorially, namely $$ \sum_{i=0}^n\binom{i}{k}=\binom{n+1}{k+1}\tag{1}. $$ Indeed the RHS counts the number of $k+1$ element subsets of $\{0,1\dotsc,n\}$. The LHS counts the same thing by classifying the subsets based on their maximum element. For $0\leq i\leq n$, there are $\binom{i}{k}$ subsets of $\{0,1\dotsc,n\}$ of length $k+1$ whose maximum element is $i$. Then for example $$ \sum_{r_2=1}^r\sum_{r_{1}=1}^{r_{2}}\binom{r_{1}}{1}=\sum_{r_2=1}^r\binom{r_{2}+1}{2}=\binom{r+2}{3} $$ and can easily be generalized, indeed, $$ \sum_{r_n=1}^r\sum_{r_{n-1}=1}^{r_{n}}\dotsb\sum_{r_{1}=1}^{r_{2}}\binom{r_{1}}{1}=\binom{r+n}{n+1}. $$ Another way to see the same result is to observe that $$ \begin{align} \sum_{r_n=1}^r\sum_{r_{n-1}=1}^{r_{n}}\dotsb\sum_{r_{1}=1}^{r_{2}}r_{1} &=[z^{r}]\frac{1}{(1-z)^{n}}\frac{z}{(1-z)^2}\\ &=[z^r]\frac{z}{(1-z)^{n+2}}\\ &=[z^{r-1}](1-z)^{-(n+2)}\\ &=\binom{r+n}{r-1} \end{align} $$ where $[z^m]$ extracts the coefficient of $z^m$ from the generating function. Here we have used the result that if $A(z)=\sum_{n\geq 0}a_{n}z^n$ is the generating function corresponding to the sequence $(a_n)$ then the generating function corresponding to the sequence of partial sums is given by $$ \frac{A(z)}{1-z}=\sum_{n\geq 0}\left( \sum_{k=0}^na_{k} \right)z^n. $$