# Binomial coefficients as multiple sums

I found the formula

$$\sum_{n_1=1}^{n-1} \sum_{n_2=1}^{n_1-1} \sum_{n_3=1}^{n_2-1} \cdots \sum_{n_m=1}^{n_{m-1}-1} 1 = {n-1 \choose m}$$

But I don't know how to prove it. Should I use double mathematical induction?

• it's almost impossible to understand what you meant to write. Please go to the FAQ section and quickly learn there how to use LaTeX to write mathematics properly in this site. – DonAntonio Jun 11 '13 at 11:47
• I look at the original post, and I look at the edited one and I've no idea how the editor can possibly know the above is what the OP actually meant...mind-reading? – DonAntonio Jun 11 '13 at 12:03
• Check that the formula works for $m=0$ and $m=n-1$ then use the identity $C_{n}^k = C_{n-1}^{k-1} + C_{n-1}^k$. Then it's an induction on $n$. – Tim Jun 11 '13 at 12:05
• @DonAntonio: Look not at the rendered form, but the source form of the original post. Then it seems clear that this is what the OP meant. – ShreevatsaR Jun 11 '13 at 20:04

The binomial coefficient in the RHS enumerates the subsets $A$ of size $m$ of $\{1,2,\ldots,n-1\}$. The LHS does the same thing, but choosing first the largest element $n_1$ of $A$, then its second-to-largest element $n_2\lt n_1$, until choosing its smallest element $n_m$.
• @ShreevatsaR When I answered this question, the binomial notation used in the question and in my answer was $C_{n-1}^m$. You changed it in the question and in my answer to ${}^{n-1}C_m$. And now the question is modified again, using ${n-1\choose m}$... All these notations are allright hence I wish you (and others) stop these (surely well intended but) useless interferences. Thanks in advance. – Did Jun 12 '13 at 15:50
• I was trying to be helpful to the OP, and use the same notation that he/she was familiar with: that's why I edited both the question and answer to use the same notation that was originally in the question, rather than the $C^{m}_{n-1}$ that was introduced by an edit, which I've never seen before, and which the OP would probably find confusing. I'm also unhappy about the question now using the notation $\binom{n-1}{m}$ which is not taught in many schools (am never happy about questions being edited into forms the asker wouldn't recognize), but sure, I won't edit again. – ShreevatsaR Jun 12 '13 at 16:15