Let S be a set with 2n+1 elements. Partition S into n pairs of elements, with one single element left over. We want to choose a set of n elements from S. From each pair of elements we can select 0, 1 or 2 elements. Also, we can either select or not select the single element.

Start by selecting k pairs to choose one element from. There are ways of doing this ( ways of choosing which pairs, and 2 ways of choosing which element in each pair). To bring the total number of selected elements up to n, we then need to select both elements from exactly half of the remaining n-k pairs, if n-k is even. If n-k is odd then we have to select both elements from of them, together with the single element of S. In either case, there are ways of doing this.

That shows that .