How to prove by induction that given a set $S$ of $n$ elements, the number even subsets of $S$ equals to the number of odd subsets? How do I prove by induction that given a positive integer $n\ge1$ and a set $S$ of $n$ elements, the number even subsets of $S$ equals to the number of odd subsets? For example, for $S=\{g,c\}$ there are two subsets with even cardinality: the empty set $\varnothing$ and $\{g,c\}$, as well as two subsets with odd cardinality: $\{g\}$ and $\{c\}$.
 A: Since $n\ge 1$ and is finite, you know there is at least one element of $S$.  Suppose one such is $a$.
Then the number of odd subsets of $S$ which contain $a$ is equal to the number of even subsets which do not contain $a$, and  the number of even subsets of $S$ which contain $a$ is equal to the number of odd subsets which do not contain $a$.
Adding the numbers together implies the number of odd subsets of $S$ equals the number of number of even subsets of $S$.
(This will not work when $n=0$, and the proposition would not be true as $\emptyset$ has one even subset but no odd subset).
The argument above does not use induction.  If you must use induction then

*

*The proposition is true when $n=1$ since there is one odd subset and one even subset (the empty set)

*Then the number of odd subsets of $S$ which contain $a$ is equal to the number of even subsets which do not contain $a$ which (by the inductive hypothesis) is equal to the number of odd subsets which do not contain $a$ and that is equal to the number of even subsets of $S$ which contain $a$.  Adding the pairs up proves the induction step.

A: By the binomial theorem,
$$0=(1-1)^n = \sum_{k=0}^{n}{(-1)^k \binom{n}{k}},$$ which leads to $$\binom{n}{0}+\binom{n}{2}+\binom{n}{4} +\cdots=\binom{n}{1}+\binom{n}{3}+\binom{n}{5} +\cdots.$$
The left side is the number of ways of choosing an even subset and the right side is the number of ways of choosing an odd subset. They are equal.
A: Let ${\cal P}_n$ be the power set of $[n]$. Then $|{\cal P}_0|=1$.
For any $A\in{\cal P}_n$ we obtain two elements of ${\cal P}_{n+1}$, namely $A$ and $A\cup\{n+1\}$. One of them is even, the other odd.
