6.1.24

(a)

左辺は$$n$$個の要素を持つ集合から濃度$$0,1,\ldots,n$$の部分集合の選び方の総数と等しい。 これは 6.1.23で解いたので$$2^n$$と等しいことが示せる。

(b)

係数が負の項を移項するとこれは$$n$$個の要素を持つ集合$$A=\{1,2,\ldots,n\}$$から偶数個の要素を持つ部分集合の選び方の総数と、 奇数個の要素を持つ部分集合の選び方の総数が等しいという主張と等しい。

選び方を符号化する。ある選び方について、要素$$i$$を選ぶときに$$s_i$$は"y"に、選ばないときに"n"になるとして 選び方を文字列$$s_1 \cdots s_n$$に符号化する。 明らかに要素の選び方と、"y","n"からなる長さ$$n$$の文字列は1対1に対応する。 あとはすべてのとりうる文字列について、"y"が奇数個ある文字列と偶数個ある文字列の数が等しいことを示せば良い。

文字列$$s_1\cdots s_n$$に対して$$s_1$$を"y"なら"n"に、"n"なら"y"に反転させる操作を考える。 これは"y"が奇数個ある文字列と偶数個ある文字列を1対1に対応付けるので、 "y"が奇数個ある文字列と偶数個ある文字列の数が等しいことが示された。