Bijection of sets?

Question

Let A be the set of subsets of [n] that have even size, and let B be the set of subsets of [n] that have odd size. Establish a bijection from A to B, thereby proving lAl=lBl.

I can figure it for a specific number but not in general:
If n=3
A : Zero Set, {2,3}, {1,3}, {1,2}
B : {3}, {2}, {1}, {1,2,3}

Any Ideas?

Answer 1

The number of ways to form the sets of each cardinality is given by the coefficients of Pascal's triangle:
(x+1)^n
There's 1 set with no elements,
n sets with 1 element (these are all odd sets, of course).
n(n-1)/2 sets with 2 elements (even sets) and so on.
We're interested in the sum of every other coefficient.

Now consider (x-1)^n. This gives the same expansion, only every other coefficient starting with the second will have a minus sign. Thus, add up (x+1)^n + (x-1)^n and you get twice every other coefficient of the original expansion.

So plug in x=1, then divide by 2:
((x+1)^n - (x-1)^n)/2 evaluated at x=1 is
(2^n - 0^n)/2 =
2^(n-1)
which is exactly half of the sum of all the coefficients.

Thus, the number of even sets is the same as the number of odd sets is the same as 2^(n-1).

Answer 2

specific. If X is i7b8b965ad4bca0e41ab51de7b31363a1 A (for this reason a subset of [n] of eve7b8b965ad4bca0e41ab51de7b31363a1 length), do o7b8b965ad4bca0e41ab51de7b31363a1e of two thi7b8b965ad4bca0e41ab51de7b31363a1gs to it. a million. If n is i7b8b965ad4bca0e41ab51de7b31363a1 X, eliminate the n. 2. If n is 7b8b965ad4bca0e41ab51de7b31363a1ot i7b8b965ad4bca0e41ab51de7b31363a1 X, upload the n. notice that this operatio7b8b965ad4bca0e41ab51de7b31363a1 is its ow7b8b965ad4bca0e41ab51de7b31363a1 i7b8b965ad4bca0e41ab51de7b31363a1verse, for this reason it truly is a bijectio7b8b965ad4bca0e41ab51de7b31363a1.

Answer 3

Following the suggestion given to me by the last person who asked this question (http://answers.yahoo.com/question/index;_ylt=AmPjjM0XnI4_a8YR413mYoTty6IX?qid=20070330095721AAuLLy3&show=7#profile-info-rnNEynhKaa ):

We define a function f: {S⊆[n]: |S| is odd}→{S⊆[n]: |S| is even} given by f(S) = {S∪{n} if n∉S, S∩{n} if n∈S}. This function is invertible (in fact, when extended to all of [n], it is its own inverse), thus injective, and it is also surjective (since f⁻¹(S) exists for all S in the codomain). Therefore, it is a bijection, as required.