The number of subsets of {1, 2, ..., n} with odd cardinality is ___________

Question

Accepted Answer

2^(n-1) Among all 2^n subsets of an n-element set, exactly half (i.e., 2^(n-1)) have odd size and the other half have even size. This elegant symmetry follows from the Binomial Theorem: setting x = -1 in (1+x)^n gives the alternating sum of binomial coefficients = 0, meaning C(n,0) - C(n,1) + C(n,2) - ... = 0, so the sum of odd-index coefficients equals the sum of even-index coefficients = 2^(n-1).