Compute $\sum_{i_n=1}^m\sum_{i_{n-1}=1}^{i_n}\cdots\sum_{i_1=1}^{i_2}\sum_{i_0=1}^{i_1}1 $

Question

Compute $$\sum_{i_n=1}^m\sum_{i_{n-1}=1}^{i_n}\cdots\sum_{i_1=1}^{i_2}\sum_{i_0=1}^{i_1}1 $$

I found this problem in a book that I've been trying go through labeled as "hard" I'm stuck trying to start the problem, let alone even compute it.

Thanks

Answer 1

The sum is equivalent to the number of tuples $(i_0,i_1,\dotsc,i_n)$ where $$ 1\leq i_0\leq i_1\leq\dotsb\leq i_{n-1}\leq i_n\leq m. $$ This number in turn is equivalent to the number of multisets of cardinality $n+1$ chosen from a set of size $m$ i.e. $$ \left(\!\!{m\choose n+1}\!\!\right)=\binom{m+n}{n+1} $$ by stars and bars.