What makes this equation equal to the combination equation

Question

I saw this statement: $${n \choose r}=\sum_{n_{r-2}=0}^{\left(n+1-r\right)}\left(\sum_{n_{r-3}=0}^{\left(n+1-r\right)-n_{r-2}}\left(\sum_{n_{r-4}=0}^{\left(n+1-r\right)-\left(n_{r-3}+n_{r-2}\right)}\left(...\left(\sum_{n_{1}=0}^{\left(n+1-r\right)-\sum_{k=2}^{r-2}n_{k}}\left(\sum_{n_{0}=0}^{\left(n+1-r\right)-\sum_{k=1}^{r-2}n_{k}}\left(n_{0}\right)\right)\right)\right)\right)\right)$$ somewhere, and I was curious, why is this statement true?

Answer 1

The index $n_{r-2}$ of the left-most sum indicates to consider showing the validity of the sum for integral $n\geq r\geq 2$. In order to see what's going on we look at first at a small example, let's say $r=4$. This seems to be small enough to be manageable, but should be large enough to see the essential steps.

Case $r=4$:

We obtain

\begin{align*} \color{blue}{\sum_{n_2=0}^{n-3}\sum_{n_1=0}^{n-3-n_2}\sum_{n_0=0}^{n-3-n_2-n_1}n_0} &=\sum_{n_2=0}^{n-3}\sum_{n_1=0}^{n_2}\sum_{n_0=0}^{n_2-n_1}n_0\tag{1}\\ &=\sum_{n_2=0}^{n-3}\sum_{n_1=0}^{n_2}\sum_{n_0=0}^{n_1}n_0\tag{2}\\ &=\sum_{n_2=1}^{n-3}\sum_{n_1=1}^{n_2}\sum_{n_0=1}^{n_1}n_0\tag{3}\\ &=\sum_{n_2=1}^{n-3}\sum_{n_1=1}^{n_2}\sum_{n_0=1}^{n_1}\sum_{n_{-1}=1}^{n_0}1\tag{4}\\ &=\sum_{1\leq n_{-1}\leq n_0\leq n_1\leq n_2\leq n-3}1\tag{5}\\ &=\binom{4+(n-3)-1}{4}\tag{6}\\ &\,\,\color{blue}{=\binom{n}{4}} \end{align*}

and the claim follows.

Comment:

• In (1) we change the order of summation of the left-most sum by exchanging $n_2\to n-3-n_2$.

• In (2) we change the order of the second sum $n_1\to n_2-n_1$.

• In (3) we observe the index $n_0=0$ can be skipped, since it does not contribute anything. This does also hold for the other indices.

• In (4) we do a small trick and write $n_0$ as summation of $n_0$ times $1$.

• In (5) we write the index region more conveniently. We observe the number of summands given by the index range \begin{align*} 1\leq n_{-1}\leq n_0\leq n_1\leq n_2\leq n-3 \end{align*} is the number of ordered $5$-tuples $(n_{-1},n_0,n_1,n_2,n_3)$ between $1$ and $n-3$. This number is given by the binomial coefficient in (6).

We are now well prepared to calculate OP's sum. We obtain for integral $n\geq r\geq 2$: \begin{align*} &\color{blue}{\sum_{n_{r-2}=0}^{n+1-r}\left(\sum_{n_{r-3}=0}^{n+1-r-n_{r-2}}\left(\sum_{n_{r-4}=0}^{n+1-r-\left(n_{r-3}+n_{r-2}\right)}\cdots\left(\sum_{n_{1}=0}^{n+1-r-\sum_{k=2}^{r-2}n_{k}}\left(\sum_{n_{0}=0}^{n+1-r-\sum_{k=1}^{r-2}n_{k}}n_{0}\right)\right)\right)\right)}\\ &\qquad=\sum_{n_{r-2}=0}^{n+1-r}\sum_{n_{r-3}=0}^{n_{r-2}}\sum_{n_{r-4}=0}^{n_{r-3}}\cdots\sum_{n_{1}=0}^{n_{2}}\sum_{n_{0}=0}^{n_1}n_{0}\\ &\qquad=\sum_{n_{r-2}=1}^{n+1-r}\sum_{n_{r-3}=1}^{n_{r-2}}\sum_{n_{r-4}=1}^{n_{r-3}}\cdots\sum_{n_{1}=1}^{n_{2}}\sum_{n_{0}=1}^{n_1}\sum_{n_{-1}=1}^{n_0}1\\ &\qquad=\sum_{1\leq n_{-1}\leq n_0\leq \cdots\leq n_0\leq n_{-1}\leq n+r-1}1\\ &\qquad=\binom{r+(n+1-r)-1}{r}\\ &\qquad\,\,\color{blue}{=\binom{n}{r}} \end{align*}

and the claim follows.