Use the "weirdo" method to explain why the amounts of subsets with even/odd elements are equal.

Question

I was given this identity for $n > 0$, $$\sum_{k=0}^{n} (-1)^k {n \choose k} = 0$$

I need to explain why, using the "weirdo" method, there are exactly many subsets with an even number of elements as there are subsets with an odd number of elements, and then give a combinatorial proof of the identity.

I am stuck on getting started with the "weirdo" method. Can anyone get the ball rolling with this method's use?

Answer 1

I did some googling. According to my understanding, using the "weirdo" method means that we pick a specific element, "the weirdo", and keep track of where it goes. Hence let $x \in U_n$ be weird, where $U_n$ stands for any set of $n$ elements. Let $E_n$ be the number of even-sized subsets of $U_n$ and $O_n$ be the number of odd sized partitions of $U_n$.

First consider $E_n$. We can either choose all odd-sized subsets of $U_n - \{x\}$ (of size $n-1$) and add the element $x$ or we can choose all even-sized subsets that do not include $x$ (of size $n-1$). Hence $E_n = O_{n-1} + E_{n-1}$

Then consider $O_n$. Similarly, we can either choose all even-sized subsets of $U_n - \{x\}$ (of size $n-1$) and add the element $x$ or we can choose all odd subsets that do not include $x$ (of size $n-1$). Hence $O_n = E_{n-1} + O_{n-1}$.

Thus $E_n = O_n$.

Regarding the identity, observe that $E_n = \sum_{k = 0, k \ \mathrm{even}}^{n}{n \choose k}$ and $O_n = \sum_{k=1, k \ \mathrm{odd}}^{n} {n \choose k}$ and use $E_n = O_n$.

Answer 2

Well, I know of a weird method to prove this. Let $V$ be a finite dimensional vector space of dimension $1$ over a field $k$, with generator $e_1$. One can form the complex $0\to S(V)\to S(V)\to 0$ where $S(V)$ is the symmetric algebra on $V$ and the only nonzero arrow is multiplication by $e_1$. This is an $S(V)$-free resolution of the trivial $S(V)$ module, $V$. Call this complex $C$. The Künneth formulas show that the $n$-fold tensor product of complexes $C(n)=C\otimes \cdots \otimes C$ has trivial homology in positive degrees and homology $k$ in zero degree. This means the augmented complex $C(n)\to k\to 0$ is acyclic. But $\dim_k C(n)_j = \binom nj$, and since the Euler characteristic of a complex equals the Euler characteristic of its homology, we get $$0=\sum (-1)^j \dim_k C(n)_j = \sum(-1)^j \binom nj$$

Answer 3

If $n$ is odd, then {sets of size $m$} and {sets of size $n-m$} biject by the "take the complement" map.

If $n$ is even, consider the set with one element removed instead. The subsets of $[n] = \{1, 2, \dots, n \}$ are precisely the subsets of $[n-1]$, together with the subsets of $[n-1]$ each with $n$ adjoined; among the former, even and odd biject (by the first case), while among the latter, even and odd likewise biject. Therefore they biject when both are combined.