Binomial Coefficient Identities

By the Binomial Theorem,

Set

Then

Let

The total number of subsets of X is

The number of subsets with exactly k elements is

Therefore, counting all subsets according to their size gives

Evaluate

By the Binomial Theorem,

Set x=1:

Now set x=-1:

Let

Consider all subsets of

There are

subsets in total.

Pair each subset A with

where we toggle whether 1 belongs to the subset.

One member of each pair has even size and the other has odd size.

Therefore, exactly half of all subsets have even size and half have odd size.