Question

Let abe a finite set and let a∈a. prove that the number of subsets of a that contain a1 equals the number of subsets of a that do not contain a1.

Answer 1

Here's a combinatorial proof. Suppose $A$ has $n$ elements.

For a subset to contain $a$, it must consist of at least one element. So if any given subset has $k$ elements, where $1\le k\le n$, then $a$ is not one of the other $k-1$ elements. This means the number of subsets containing $a$ is

$\displaystyle\sum_{k=1}^n\binom11\binom{n-1}{k-1}$

Put another way, we are choosing elements from $A$ to form a subset of $k$ elements. We want $a$ to be in each subset, so we have $n-1$ other elements of $A$ from which to choose. Then we sum over all the possible sizes of the desired subset.

On the other hand, if we want to build subsets not containing $a$, then we have $n-1$ total elements to choose from, and we can make subsets of size ranging from 0 to $n-1$, so the number of subsets not containing $a$ is

$\displaystyle\sum_{k=0}^{n-1}\binom10\binom{n-1}k$

We have $\dbinom10=\dbinom11=1$, and in the second sum we can shift the index up by 1 to get

$\displaystyle\sum_{k=1}^{n-1+1}\binom10\binom{n-1}{k-1}$

which is the same as the first count.