- #1
ploppers
- 15
- 0
Homework Statement
Show that there is a one to one correspondence between even and odd subsets of the set {0, 1...n}.
Homework Equations
They want a combinatorial proof so basically a proof based on counting?
Perhaps (n choose k) = (n choose n-k)
The Attempt at a Solution
I've solved this problem algebraically by expanding (1-1)^n, however, I do not understand, by counting, how there are the same amount of even subsets as odd. I tried expanding the factorials and trying to simplify but it proved to be unsuccessful. This is the 1st problem of the problem set, I have a feeling that the solution is very simple.