The discussion revolves around the evaluation of a proof for Generalized Vandermonde's Identity, specifically focusing on the requirements for a successful proof using a story proof or double counting approach. Participants are analyzing the proof submitted by the original poster and suggesting areas for improvement.
Participants generally agree that the proof lacks sufficient detail and clarity, particularly regarding the double counting argument and the summation's role. However, there is no consensus on the specific improvements needed or the exact nature of the shortcomings.
The discussion highlights limitations in the original proof's clarity and completeness, particularly in addressing the requirements of the assignment to avoid algebra or induction methods.
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 }.$$
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.