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?

  • 5
    $\begingroup$ 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. $\endgroup$ – DonAntonio Jun 11 '13 at 11:47
  • 1
    $\begingroup$ 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? $\endgroup$ – DonAntonio Jun 11 '13 at 12:03
  • $\begingroup$ 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$. $\endgroup$ – Tim Jun 11 '13 at 12:05
  • $\begingroup$ @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. $\endgroup$ – 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$.

  • $\begingroup$ @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. $\endgroup$ – Did Jun 12 '13 at 15:50
  • $\begingroup$ 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. $\endgroup$ – ShreevatsaR Jun 12 '13 at 16:15
  • $\begingroup$ We are here after all to help people asking the questions, and using notation unfamiliar to them (without telling them what it means) is not the best way to do so. Also I wish to clarify: I usually don't edit answers, but in this case it seemed evident that you were simply following the question in the choice of notation, and I assumed the reason was that you too wished to be helpful to the OP and use the same notation. (So since the notation in the question was not what the OP used, I changed both.) It seems this assumption was wrong, and I was mistaken. I won't edit your answers again. $\endgroup$ – ShreevatsaR Jun 13 '13 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.