How to prove this strange combinatorical identity?

Question

Let $n\in\mathbb{N}$. I observed today that $$1+n+\sum_{i_1=1}^ni_1+\sum_{i_2=1}^{n}\sum_{i_1=1}^{i_2}i_1+\sum_{i_3=1}^n\sum_{i_2=1}^{i_3}\sum_{i_1=1}^{i_2}i_1+\dots + \sum_{i_{n-1}}^n\sum_{i_{n-2}=1}^{i_{n-1}}\dots\sum_{i_1=1}^{i_2}i_1=\frac{(2n)!}{(n!)^2}$$ I'm wondering how this identity can be proven. Note that there are $n+1$ terms on the LHS.

Answer 1

Ignoring the initial $1$ on the LHS, you can write the $k^{th}$ term on the LHS as $$ \sum_{i_1=1}^n\sum_{i_2=1}^{i_1}\cdots \sum_{i_k=1}^{i_{k-1}}i_k=\sum_{i_1=1}^n\sum_{i_2=1}^{i_1}\cdots \sum_{i_k=1}^{i_{k-1}}\sum_{i_{k+1}=1}^{i_k}1 $$ Since we are summing the number $1$, the value of the summation is just equal to the number of ways to choose the indices.

A choice of indices is a weakly decreasing list $n\ge i_1\ge i_2\ge \dots \ge i_k\ge i_{k+1}\ge 1$. Choosing these is equivalent to choosing a multi-set of $[n]$ of size $k+1$, the number of which is $\binom{n+k}{n-1}$. Therefore, the LHS is $$ 1+\binom{n}{n-1}+\binom{n+1}{n-1}+\dots+\binom{2n-1}{n-1}, $$ and the result follows by the hockey stick identity.

Answer 2

Fix $1\leqslant p\leqslant 2n$ and let $A_p$ denote the number of ways to choose an $n$ element subset $T$ of $\{1, \ldots, 2n\}$ with $\max T=p$. Note that $A_p=0$ for $p<n$, $A_n=1$, and for $1\leqslant j\leqslant n$, $$A_{n+j}=\sum_{i_j=1}^n\ldots \sum_{i_2=1}^{i_3} \sum_{i_1=1}^{i_2}1 = \sum_{i_j=1}^n\ldots \sum_{i_2=1}^{i_3}i_2.$$ Summing over $p$ gives the number of $n$ element subsets of $2n$, which is $\binom{2n}{n}$, your right side, and it is also equal to $\sum_{p=n}^{2n}A_p$, which is your left side.