There are like forty different ways to do this. Three approaches:

1) Let . Show that can be partitioned into two blocks, the elements of and the elements of united with . Conclude that if then .

2) Note that (why?)

3) Show that by showing that by mapping to (the indicator function) is a bijection.