Suppose that (x1, x2, ..., xn) is a vector of numbers.

Question

If each xi is either 0 or 1, determine the number of vectors such that their sum x1 + x2 + . . . + xn is odd.

Answer 1

There are 2ⁿ combinations of n 1's and 0's.

Exactly 1/2 of these will have an odd sum:  # odd sums = 2^n-1

 

As an example, consider n=3.   2³=8, we expect 2²=4 entries to have odd sums:

000, 001, 010, 011, 100, 101, 110, 111