Problem 1043

There are essentially two ways to approach an exercise of this type. The first is a brute force induction proof, generally using Pascal's formula for the propagation step. The second method is a combinatorial proof. This method involves counting the cardinality of the same well-chosen set in two different ways, which directly reveals an equality. This method is often shorter and more pleasant, and we will use it here.

The idea is to calculate in two different ways the number of subsets with $n$ elements of a set with $2n+1$ elements. This number is equal to $\binom{2n+1}{n}$, the right-hand side of our equality. Let's now try to bring out the left-hand side. By observing this term, we see a $2^k$ term, which corresponds to $k$ binary choices, and a $\binom{n}{k}$ term, corresponding to the choice of $k$ elements. By putting these two elements together, we arrive at the following method of calculation.

Group our $2n+1$ elements into $n$ pairs, and set the last element aside. Choose $k$ of these pairs $\left(\binom{n}{k}\right.$ choices). The number $k$ corresponds to the number of pairs containing exactly one element of our set with $n$ elements: in each of these $k$ pairs, choose one of the two elements ($2^k$ choices). We have selected $k$ elements, and we need to choose $n-k$ more to end up with a set of $n$ elements. These $n-k$ elements must be grouped into $\lfloor(n-k) / 2\rfloor$ pairs, and if $n-k$ is odd, to complete, we add to our set the element not belonging to any pair. It is immediately clear that we thus construct each set of $n$ elements once, and that there are $\sum_{k=0}^{n} 2^{k}\binom{n}{k}\binom{n-k}{\lfloor(n-k) / 2\rfloor}$ ways to perform this construction.