Home » Uncategorized » Binomial coefficients as multiple sum

Binomial coefficients as multiple sum

Prove that

    \[\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 = \binom{n-1}{m}\]

Solution

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 <  n_1, until choosing its smallest element n_m.

Read more

 


Leave a comment

Donate to Tolaso Network