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.