Combinatorial counting problem

[ploppers]

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.

 

[LCKurtz]

What does "even subset" mean? Do you mean subsets having an even number of elements or subsets consisting of only even numbers?

My guess is the second interpretation. And if you show the "even" sets and "odd" sets have the same number of elements, wouldn't that do it?

 

[Count Iblis]

I've solved this problem algebraically by expanding (1-1)^n...

You have:

0 = (1-1)^n = Sum from k = 0 to n of Binomial[n,k](-1)^k =

(add up the even and odd k separately) =

#even subsets - #odd subsets.

 

[ploppers]

Even and odd subsets mean choosing an even amount or odd amount. For example, 4 choose 3 would be an odd subset while 4 choose 2 would be even. Thanks for the responses, that was exactly what I did to prove it algebraically, however, what would the combinatorial proof be?

I've tried to solve the problem further by comparing the relationship between choosing 2i +1 numbers and 2i numbers. (nC2i + 1) = (nC2i)(n - 2i)/(2i + 1). When I sum these, I don't see how they could ever equal...