Prove $\binom{n}{k_1,...,k_m} = \sum_{i=1}^m \binom{n - 1}{k_1,...,k_{i - 1},..,k_m}$

Question

I have a question ask to prove $$\binom{n}{k_1,...,k_m} = \sum_{i= 1}^m \binom{n - 1}{k_1,...,k_{i - 1},..,k_m}$$ I'm not sure how to approach this question, but the only thing that I noticed the LHS is similar to Multinomial theorem. Any suggestion help me go further?

Answer 1

First, it's $k_i - 1$ not $k_{i - 1}$. Second, it's just the multinomial version of Pascal's rule:

$$ \binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}. $$

Remember the proof? Either the element '$n$' is in the subset or not? It's exactly the same argument except instead of a binary choice for the element '$n$', you have $m$ choices.