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

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.
  • #1
12
1
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:
Mathematics news on Phys.org
  • #2
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.
 
  • #3
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.
 
  • #4
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##.
 

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

Replies
2
Views
665
Replies
11
Views
1K
Replies
13
Views
1K
Replies
11
Views
1K
Replies
7
Views
1K
Replies
12
Views
1K
Replies
11
Views
954
Back
Top