Prove that $\displaystyle \cup_{i=0}^{k} P_{i} x P_{k-i} \rightarrow P_{k}(X \cup Y)$ is a bijection (For X and Y disjoint sets) defined by (A,B) --> (AUB). (by P_k(X) I mean the power set of X, that is all of the possible subsets of X of cardinality k)

Deduce that:

$\displaystyle {m+n \choose k} = \sum_{i = 0}^{k} {m \choose i} {n \choose k- i} $

I have what (I think) are the makings of a proof of both parts but I'm really stuck.

If we take A⊆X and B⊆Y where A∪B ⊆X∪Y. Consider C⊆X∪Y which can be broken up into: C=C∩X+C∩Y since X and Y are disjoint. Then we can then map: f:P(X)× P(Y)→P(X∪Y) by f(A,B)= A∪B. Which has inverse f^(-1) (C)=(C∩X,C∩Y). If we look at sets of a particular size: if |A|= i and |B|= k-i then since X and Y are disjoint, and since they are disjoint we know |A∪B|= k We also know that since A is a subset of X and B is a subset of Y and in particular A is a subset of X with cardinality i and B is a subset of Y of cardinality k-i we know that A∈P_i (X) and B∈P_(k-i) (Y).

Inversely if If we take |C|=k then |C∩X+C∩Y|=k and |C∩X|+|C∩Y|=k. We now consider P_i (X)× P_(k-i) (Y)→P_k (X∪Y) as an injection we have to modify the domain for it to be a bijection. Looking at inverse function above with a new cardinality we take f^(-1):P_k (X∪Y)→$\displaystyle \cup_{i=0}^{k}$P_i (X)× P_(k-i) (Y) 〗 by g(C)=(C∩X),(C∩Y) since this has to map to the union of all of the P_i (X)× P_(k-i) (Y)as i varies from 0 to k in order to be well defined (since C∈P_k (X∪Y) and can have cardinalities between 0 and k. And now with a well defined inverse we can amend the domain of the original function such that: ⋃_(i=0)^k〖P_i (X)× P_(k-i) (Y)→P_k (X∪Y)〗 by f(A,B)= A∪B as stated in the beginning which is now not just an injection but also a bijection.

For the second part I have:

We define ((m+n)¦k)=|P_k (Z) | where |Z|=m+n in the same vein the right hand side can be re-written: ∑_(i=0)^k: (m¦i)(n¦(k-i)) =∑_(i=0)^k〖|P_i (X) ||P_(k-i) (Y)|〗 where |X|=m & |Y|=n. We can rewrite Z=X∪Y so now the problem looks like this: |P_k (X∪Y) |=∑_(i=0)^k▒〖|P_i (X) ||P_(k-i) (Y)|〗. P_k (X∪Y)is the union of all the subsets of (X∪Y) of cardinality k. So the cardinality of that is the number of possible subsets of size k. And I have no idea….

(Sorry I'm not very good with trying to do math symbols online. To make it easier here's a link to an image of what I wrote: http://pic100.picturetrail.com/VOL71.../383315256.jpg

It's also attached (Hopefully) I originally wrote it in a .docx file but I can't seem to upload it here anyway...

Thanks for any help. I'm really quite stuck!