Counting subsets of a finite set of integers

Question

Let S be a set of n distinct integers and A be any subset of S. Let σ(A) be the sum of the elements of A, e.g. σ(A) = 4 if A = {1,2,3} (be sure to include the empty set, for which the sum of elements is 0). How many subsets A of S are there such that σ(A) is even?

Answer 1

First of all, the question contains an error, which should not cause much confusion. It should be "σ(A) = 6 if A = {1,2,3}" instead of "σ(A) = 4 if A = {1,2,3}".



There are two possible scenarios: one is that the set S contains only even numbers, the other is that it contains at least one odd number. In case one, the sum of elements of every subset is even, so the required number is the same as the number of subsets of S, which is 2ⁿ. Case two is a bit more complicated and the answer is 2^n-1. Suppose we start with a set with only one odd number. Then the only subset of which the sum of elements is even has to be the empty set. Therefore the required number is 1 = 2^1-1. Suppose that this is true for a set S containing n integers. Since such a set has 2ⁿ subsets in total, and by the hypothesis, there are half of them for which the sum of elements is even, the other half then must be those for which the sum of elements is odd. Now consider a set S' containing n+1 integers. We can think of this set as formed by adding an extra integer to a set S containing n integers, for which half of subsets are "even" and half are "odd" in the sense that the sum of their elements is even or odd, respectively. Disregarding the parity of this newly added integer (the (n+1)-th added to the set S) being even or odd, adding this integer to every subset of the previous subsets of S will create the same number of "even" and "odd" subsets of the set S', effectively doubling the number of subsets of each type. Therefore the number of subsets of S' of which the sum of elements is even becomes 2ⁿ = 2^n+1-1. This completes the recursion step of mathematical induction. Thus we have proved that the number in case two is 2^n-1.

A final remark: The requirement that the numbers in the set are distinct seems unnecessary.