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

  • #1
12john
13
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##.
 

Similar threads

Replies
0
Views
1K
Replies
125
Views
18K
Replies
5
Views
2K
6
Replies
175
Views
23K
Replies
1
Views
3K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
3K
Back
Top