How to simplify $\sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\sum_{a_3=1}^{a_2}\dots\sum_{a_{k+1}=1}^{a_k}1$ Let
$$x=\sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\sum_{a_3=1}^{a_2}\dots\sum_{a_{k+1}=1}^{a_k}1$$
where $n,k\in\mathbb{Z}^+$. How to simplify $x$?
I simplified it for $k=1,2,3$ and I got $n$, $\dfrac12n(n+1)$ and $\dfrac16n(n+1)(n+2)$. From this I assumed that for any $k$:
$$x=\dfrac n{k+1}{\binom{n+k}{n}}$$
Problem is how to prove it. I tried using mathematical induction, but it seems that this is not an easy way.
 A: The sum is the same as the number of ways for choosing $(k+1)$-tuple $(a_1,a_2,\ldots,a_{k+1})$ such that $1\leq a_{k+1}\leq a_{k}\leq \ldots a_1$. The different possibilities can be broken down as follows:


*

*All number are distinct: This is same as choosing $k+1$ distinct numbers from the set $\{1,2,\ldots,n\}$ sorting them. Thus, this can happen in $\binom{n}{k+1}$ ways.

*$l$ repetitions are allowed: We note that repetitions happen only at consecutive locations as the tuples entries are in the descending order. Therefore, there are $\binom{k}{l}$ possible locations for repetition. Therefore, we first choose $k-l$ distinct numbers from the set $\{1,2,\ldots,n\}$ and $l$ locations for repetition, to form a valid tuple. Thus, this can happen  in $\binom{n}{k+1-l}\binom{k}{l}$  ways.


Thus, we have
\begin{align}
\sum_{a_1=1}^{n}\sum_{a_2=1}^{a_1}\ldots \sum_{a_{k+1}=1}^{a_{k}}1 &= \sum_{l=0}^{k} \binom{n}{k+1-l}\binom{k}{l} \\
&=\sum_{l=0}^{k+1} \binom{n}{k+1-l}\binom{k}{l} - \binom{n}{0}\binom{k}{k+1}\\
&= \binom{n+k}{k+1}.
\end{align}
Here, we use Vandermonde's identity to get the last step.
The result also agrees with your formula: 
\begin{equation}\frac{n}{k+1}\binom{n+k}{n} = \frac{n(n+k)!}{n!k!(k+1)}=\frac{(n+k)!}{(n-1)!(k+1)!} =\binom{n+k}{k+1}.
\end{equation}
