Pattern with the the tetration of summations.

Question

While dealing with a question with finding an explicit form for a sequence I noticed something:

$$\sum_{x_0=0}^{n-1} 1=\frac{n}{1!}$$

$$\sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} 1=\frac{n(n-1)}{2!}$$

$$\sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \sum_{x_2=0}^{x_1-1} 1= \frac{n(n-1)(n-2)}{3!}$$

$$\sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \sum_{x_2=0}^{x_1-1} \sum_{x_3=0}^{x_2-1} 1= \frac{n(n-1)(n-2)(n-3)}{4!}$$ ...

Question:

How can I prove the pattern I am seeing?

I'm thinking about induction in which case the base case is proved. But then assuming $p(n)$ is true I need to show $p(n+1)$ is true. But how can I write $p(n)$ as notation is troubling me, and how can I go from there.

Answer 1

Note we can develop a combinatorial argument which gives total number of ways as ${n\choose r}$ where r is total number of summations

Answer 2

I will change your notation a bit and use $x_{-1}\equiv n$ instead.

Hint: for $m>0$, $$ \sum_{x_{0}=0}^{x_{-1}-1}\cdots\sum_{x_{m}=0}^{x_{m-1}-1}1=\sum_{x_{0}=0}^{x_{-1}-1}\left[\sum_{x_{1}=0}^{x_{0}-1}\cdots\sum_{x_{m}=0}^{x_{m-1}-1}1\right]=\cdots $$ You should use an induction hypothesis on the inner sum at this point.

Answer 3

It's a cascasded form of the summation along a diagonal of Pascal's triangle, otherwise known as the hockey stick identity, i.e. $$\sum_{r=0}^m \binom ra=\binom {m+1}{a+1}$$ Assume $p$ levels of cascaded summations. Working from inside out we have $$\begin{align} &\quad \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \sum_{x_2=0}^{x_1-1}\cdots \sum_{x_{p-3}=0}^{x_{p-4}-1} \sum_{x_{p-2}=0}^{x_{p-3}-1} \sum_{x_{p-1}=0}^{x_{p-2}-1} \quad \quad 1\\ &= \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \sum_{x_2=0}^{x_1-1}\cdots \sum_{x_{p-3}=0}^{x_{p-4}-1} \sum_{x_{p-2}=0}^{x_{p-3}-1} \underbrace{\sum_{x_{p-1}=0}^{x_{p-2}-1} \binom{x_{p-1}}0}\\ &= \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \sum_{x_2=0}^{x_1-1}\cdots \sum_{x_{p-3}=0}^{x_{p-4}-1} \underbrace{\sum_{x_{p-2}=0}^{x_{p-3}-1} \quad\binom{x_{p-2}}1}\\ &= \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \sum_{x_2=0}^{x_1-1}\cdots \underbrace{\sum_{x_{p-3}=0}^{x_{p-4}-1} \quad \binom{x_{p-3}}2}\\\\ &=\qquad\vdots\\\\ &= \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \underbrace{\sum_{x_2=0}^{x_1-1} \binom{x_2}{p-3}}\\ &= \sum_{x_0=0}^{n-1} \underbrace{\sum_{x_1=0}^{x_0-1} \;\;\;\binom{x_1}{p-2}}\\ &= \underbrace{\sum_{x_0=0}^{n-1} \quad\binom{x_0}{p-1}}\\ &= \qquad\binom{n}{p} \end{align}$$ i.e. $$\color{red}{\boxed{\sum_{x_0=0}^{n-1}\sum_{x_1=0}^{x_0-1}\sum_{x_2=0}^{x_1-1} \cdots \sum_{x_{p-1}=0}^{x_{p-2}-1}1=\binom np}}$$ Putting $p=4$ gives the final equation in your question, i.e. $$\begin{align} &\quad \sum_{x_0=0}^{n-1}\sum_{x_1=0}^{x_0-1}\sum_{x_2=0}^{x_1-1} \sum_{x_{3}=0}^{x_{2}-1}1\\ &=\sum_{x_0=0}^{n-1}\sum_{x_1=0}^{x_0-1}\sum_{x_2=0}^{x_1-1}\binom{x_2}1\\ &=\sum_{x_0=0}^{n-1}\sum_{x_1=0}^{x_0-1}\binom{x_1}2\\ &=\sum_{x_0=0}^{n-1}\binom{x_0}3\\ &=\binom n4\\ &=\frac {n(n-1)(n-2)(n-3)}{4!}\end{align}$$