Question

Give a combinatorial proof of Corollary \({\bf{2}}\) of Section \({\bf{6}}.{\bf{4}}\) by setting up a correspondence between the subsets of a set with an even number of elements and the subsets of this set with an odd number of elements. (Hint: Take an element a in the set. Set up the correspondence by putting a in the subset if it is not already in it and taking it out if it is in the subset.

Short answer

Hence, the given statement is verified,

\(\sum\limits_{i = 0}^n {{{( - 1)}^k}} \left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right) = 0\).

Step-by-step solution

Concept introduction

A set A is a subset of a set B if all of A's elements are also elements of B; B is therefore a superset of A in mathematics. It's possible that A and B are equal; if they're not, A is a legitimate subset of B. Inclusion describes the relationship between two sets when one is a subset of the other.

Solution

Let\(S\)be a set with\(|S| = n\). Consider\({S_1}\)and\({S_2}\), the sets of subsets of\(S\)with even and odd cardinalities respectively. If\(x\)is an element of\(S{\rm{ and }}x \in A\)for some\(A \subseteq S\), take out\(x\)so that\({f_x}(A) = A\backslash \{ x\} \)is the new subset; otherwise add\(x\)to the subset\(A\)so that\({f_x}(A) = A \cup \{ x\} \).

Observe that if the same operation is performed on\({f_x}(A)\)then we back\(A\)in either cases, i.e.\({f_x}\left( {{f_x}(A)} \right) = A\). Moreover there is no other\(C \subseteq S\)so that we can get\({f_x}(A)\)from it using this method unless\(C = A\). Observe that whenever\(A \in {S_1} \Rightarrow {f_x}(A){\rm{ }}\)in\({S_2}\)and vice-versa.

Thus there is a one-to-one correspondence between\({S_1}\)and\({S_2}\)via the function\({f_x}\)which is clearly a one-to-one function from\({S_1}\)to\({S_2}\). Thus\(\left| {{S_1}} \right| = \left| {{S_2}} \right|\)or in other words

\(\sum\limits_i {\left( {\begin{array}{*{20}{c}}n\\{2i}\end{array}} \right)} = \sum\limits_i {\left( {\begin{array}{*{20}{c}}n\\{2i + 1}\end{array}} \right)} \Rightarrow \sum\limits_{i = 0}^n {{{( - 1)}^k}} \left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right) = 0\)

Therefore, the given statement is verified,

\(\sum\limits_{i = 0}^n {{{( - 1)}^k}} \left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right) = 0\)