# Why did I lose 60% on my proof of Generalized Vandermonde's Identity?

• I
12john
My tests are submitted and marked anonymously. I got a 2/5 on the following, but the grader wrote no feedback besides that more detail was required. What details could I have added? How could I perfect my proof?
Prove Generalized Vandermonde's Identity, solely using a story proof or double counting. DON'T prove using algebra or induction — if you do, you earn zero marks.

$$\sum\limits_{k_1+\cdots +k_p = m} {n_1\choose k_1} {n_2\choose k_2} \cdots {n_p\choose k_p} = { n_1+\dots +n_p \choose m }.$$

Beneath is my proof graded 2/5.
I start by clarifying that the summation ranges over all lists of NONnegative integers ##(k_1,k_2,\dots,k_p)## for which ##k_1 + \dots + k_p = m##. These ##k_i## integers are NONnegative, because this summation's addend or argument contains ##\binom{n_i}{k_i}##.

On the LHS, you choose ##k_1## elements out of a first set of ##n_1## elements; then ##k_2## out of another set of ##n_2## elements, and so on, through ##p## such sets — until you've chosen a total of ##m## elements from the ##p## sets.

Thus, on the LHS, you are choosing ##m## elements out of ##n_1+\dots +n_p##, which is exactly the RHS. Q.E.D.

Last edited:

Mentor
Can't read the mind of the person who graded it, but you could have made clearer why (or at least mention that) the sum catches every possible way to select m elements. You only documented that every "element" of the LHS is part of the RHS, i.e. LHS <= RHS.

Mentor
2022 Award
I miss a comment on the summation. And the product is only implicitly explained. Where is the double counting? I would have expected an argument ##\sum \ldots = ?## but you have looked at the RHS and reasoned from there instead of the other way around.

Staff Emeritus
$$\binom{n_1}{k_1}\binom{n_2}{k_2} \cdots \binom{n_p}{k_p} = \binom{n_1+\cdots+n_p}{m}$$ as long as ##m=k_1+\cdots+k_p##.