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

• I
• 12john
In summary, the conversation discusses a proof of Generalized Vandermonde's Identity using a story proof or double counting. The proof presented received a grade of 2/5 and the grader provided feedback that more details were needed. The proof involves choosing elements from sets and the summation is clarified to range over all lists of nonnegative integers that add up to m. The proof also explains how the RHS and LHS are equivalent and addresses the issue of double counting. However, the proof is criticized for not explicitly explaining the double counting and for not starting from the LHS.

#### 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:
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.

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.

To put what the others said in another way, the way I read your proof, you seem to be saying
$$\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##.