Suppose we have the following two identities: ∑ k = 0 n ( n k ) = 2 n ∑ k = 0 n ( − 1 ) k ( n k ) = 0 The first says that the number of subsets of an n-set is 2 n . The second says that the number of subsets of even size equals the number of subsets of odd size (of an n-set). Thus there are 2 n − 1 subsets of even length and 2 n − 1 subsets of odd length?To combinatorially prove the second identity, let A be a k-subset of [ n ]. Then note whether k is odd or even?

Question

Suppose we have the following two identities:            ∑              k        =        0                    n                                      (                            n        k                              )                      =          2      n                  ∑              k        =        0                    n              (    −    1          )              k                                      (                            n        k                              )                      =    0  The first says that the number of subsets of an   n-set is       2    n  . The second says that the number of subsets of even size equals the number of subsets of odd size (of an   n-set). Thus there are       2          n      −      1       subsets of even length and       2          n      −      1       subsets of odd length?To combinatorially prove the second identity, let   A be a   k-subset of   [  n  ]. Then note whether   k is odd or even?

Miguel Shah · Accepted Answer

The second identity can be proven by an inclusion-exclusion argument, but maybe it&#039;s clearer this way: pick an arbitrary element of the 𝑛-element set. Given a subset, if it contains the arbitrary element, remove it; otherwise, add it in. (That is, take the symmetric difference.) This defines a bijection from the set of subsets of odd size and the subsets of even size.The generalization with 2 replaced by a larger integer is less trivial.

Landen Salinas · Accepted Answer

From another point of view you have:                    (                  1          +          1                )            n        =      2    n    =      ∑          k      =      0        n                                (                            n        k                              )                                        1                  n          −          k                                    1        k              =      ∑          k      =      0        n                                (                            n        k                              )                    and                    (                  1          −          1                )            n        =  0  =      ∑          k      =      0        n                                (                            n        k                              )                                        1                  n          −          k                                                          (                          −              1                        )                          k              =      ∑          k      =      0        n                      (                  −          1                )              k                                (                            n        k                              )

Suppose we have the following two identities: Sum_(k=0)^n (n k)=2^n Sum_(k=0)^n (−1)^k (n k)=0

Answered question

Answer & Explanation

New Questions in Precalculus