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}