Question

Help with understanding Chu-Vandermonde's identity proof. The identity states \[\sum_{k=0}^{n}\left(\begin{matrix}a \\ k\end{matrix}\right)\left(\begin{matrix}b \\ n-k\end{matrix}\right)=\left(\begin{matrix}a+b \\ n\end{matrix}\right)\]

Answer 1

I found this proof here: http://www.proofwiki.org/wiki/Chu-Vandermonde_Identity but I find it confusing at the "last" step where the index on the second sum changes from (n-k) to just k. I'm not sure how the multiplication with the 2 sums results in these indices at the last step. (It's also "confusing" in the sense that they don't fully write what they're summing from what to what)

The link from wikipedia http://en.wikipedia.org/wiki/Vandermonde%27s_identity seems even more confusing to me because I don't understand how they changed their indices. I think I just have trouble manipulating double summations =\.

Answer 2

i think we can say this in simple english
lets say we have \(a+b\) people, \(a\) women and \(b\) men
the right hand side is the number of ways you can pick \(n\) people out of the total

instead we can divide the group up in to women and men, and pick \(n\) out of them as follows
1) no women, \(n\) men or
2) 1 woman, \(n-1\) men or
3) 2 women, \(n-2\) men or in general

\(k\) women and \(n-k\) men
all these possibilities added together are the number of ways to choose n out of \(a+b\)