2
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Patrick Stevens, user147263, user251257, John B, user228113 Mar 2 '16 at 1:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 9
    $\begingroup$ You shouldn't assume we know what the weirdo method is! $\endgroup$ – Pedro Tamaroff Mar 1 '16 at 23:07
  • 1
    $\begingroup$ I know a combinatorial way to do this and an algebraic way to do this and a way that I might not use either of those words for, but I have no idea what "weirdo" means in this context. $\qquad$ $\endgroup$ – Michael Hardy Mar 1 '16 at 23:08
  • $\begingroup$ @PedroTamaroff It shows up here: books.google.se/… $\endgroup$ – Étienne Bézout Mar 1 '16 at 23:11
  • $\begingroup$ The usual way to show this is by the binomial theorem, by the way: it's precisely the expansion of $(1-1)^n$. $\endgroup$ – Patrick Stevens Mar 1 '16 at 23:20
  • 1
    $\begingroup$ The book that @ÉtienneBézout provided is the exact book I am using. I honestly don't even know what the "weirdo" is supposed to be, I was wondering if it was known here. I have a hint for the problem that states, "Choose a weirdo, w, and match eat set with w to a set without w." $\endgroup$ – Dewick47 Mar 1 '16 at 23:39
2
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ $S_n$ standing for a set of $n$ elements is not nice notation. =) $\endgroup$ – Pedro Tamaroff Mar 1 '16 at 23:42
  • $\begingroup$ @PedroTamaroff Okay, you're right! I'll change it :) (Assuming you were referring to confusion with the symmetric group) $\endgroup$ – Étienne Bézout Mar 1 '16 at 23:43
  • $\begingroup$ This answer is what I was looking for and the explanation really helped me understand the point of the question. $\endgroup$ – Dewick47 Mar 2 '16 at 0:08
  • $\begingroup$ @dewick49 Great! If you think I answered your question, please consider "accepting" my answer. $\endgroup$ – Étienne Bézout Mar 2 '16 at 0:12
2
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ thank you. i thought it was clear that this is what the OP meant by "weirdo method." $\endgroup$ – Elliot G Mar 1 '16 at 23:16
  • $\begingroup$ The question has inverted commas around the word weirdo. This approach is weird for real $\ddot{\smile}$. $\endgroup$ – Rob Arthan Mar 1 '16 at 23:26
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.