Question

Show that a nonempty set has the same number of subsets with an odd number of elements as it does subsets with an even number of elements.

Short answer

The required expression is \(\sum\limits_{k = 1}^{\left\lceil {\frac{n}{2}} \right\rceil } {\left( {\begin{array}{*{20}{c}}n\\{2k - 1}\end{array}} \right)} = \sum\limits_{k = 0}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {\left( {\begin{array}{*{20}{c}}n\\{2k}\end{array}} \right)} \).

Step-by-step solution

Formula of Pascal identity

Pascal identity:

\(\left( {\begin{array}{*{20}{c}}{n + 1}\\k\end{array}} \right) = \left( {\begin{array}{*{20}{c}}n\\{k - 1}\end{array}} \right) + \left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right)\)

Show a nonempty set has the same number of subsets with an odd number of elements by Pascal identity

Suppose the nonempty set \(S\) has \(n > 0\) elements.

The no. of subsets of \(S\) with odd no. of elements is \(\sum\limits_{k = 1}^{\left( {\frac{n}{2}} \right)} {\left( {\begin{array}{*{20}{c}}n\\{2k - 1}\end{array}} \right)} \) while the no. of subsets of \(S\) containing even no. of elements is \(\sum\limits_{k = 0}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {\left( {\begin{array}{*{20}{c}}n\\{2k}\end{array}} \right)} \).

Corollary 2 implies the following:

\(\begin{array}{l}\sum\limits_{k = 0}^n {{{( - 1)}^k}} \cdot \left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right) = 0\\\sum\limits_{k = 1}^{\left\lceil {\frac{n}{2}} \right\rceil } {\left( {\begin{array}{*{20}{c}}n\\{2k - 1}\end{array}} \right)} = \sum\limits_{k = 0}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {\left( {\begin{array}{*{20}{c}}n\\{2k}\end{array}} \right)} \end{array}\)