How many even subsets are there?

[xnull]

Given a finite set $$S$$ of cardinality m:
Decide how many even or odd subsets there are of S (finding one should give you the other).

Here is what I've done so far.

First, I looked to a multiplication out by hand.

(m * (m-1)) + (m * (m-1) * (m-2) * (m-3)) + (m * (m-1) * (m-2) * (m-3) * (m-4) * (m-5)) + ...

Well, I noticed I could factor (m * (m-1)) out which gives

(m * (m-1)) * (1 + ((m-2) * (m-3)) + ((m-2) * (m-3) * (m-4) * (m-5)) + ...)

Inside the second group of parenteses I noticed I could factor out ((m-2) * (m-3)) and so on

(m * (m-1)) * (1 + ((m-2) * (m-3) * (1 + ((m-4) * (m-5) * (1 + ... )))))))

Because this was a tad ugly I made a recurrence relation from it

$$R_{k} = 0$$
$$R_{i} = (m-2i)(m-2i-1)(1+R_{i+1})$$
$$R_{0}$$ would give the solution for the number of even subsets.

I can't seem to find the closed form.

This is the only direction I've gone with the problem so far.

Does anyone have any directions to go on this or a previously published solution to the problem? I looked all over and couldn't find one but it's the kind of problem I would expect to have already been solved.

 

[xnull]

Solved it.

Heh. Silly to have missed it.

$$2^{m-1}$$ even subsets and odd subsets.

 

[JSuarez]

Remember that the number of subsets (of a set with m elements) with k elements is given by:

$$\binom{m}{k}$$

Now, from the binomial theorem (or the fact that there are as many odd subsets as even ones) and the fact that the total number of subsets is 2^m, you should be able to deduce that the number of odd subsets is:

$$\sum_{k\;odd}\binom{m}{k}=2^{m-1}$$