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.

Here's a combinatorial proof. Suppose has elements.

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



Put another way, we are choosing elements from to form a subset of elements. We want to be in each subset, so we have other elements of 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 , then we have total elements to choose from, and we can make subsets of size ranging from 0 to , so the number of subsets not containing is



We have , and in the second sum we can shift the index up by 1 to get



which is the same as the first count.