Show that $1= \sum_{k=0}^{m} (-1)^k {m \choose k}2^{m-k}$ using sign reversing involution

Question

Using the sign reversing involution, how can I show that $$1= \sum_{k=0}^{m} (-1)^k {m \choose k}2^{m-k}.$$ I have been trying to figure out the what the signed sets are namely $S^{ +}$ and $S^{ -}$. Can anyone please give me a hint to what the signed sets should be and perhaps the involution map defined on the disjoint union of the two signed sets?

Answer 1

Let $S$ be the set of pairs $(A,B)$ where $A$ and $B$ are disjoint subsets of $[m]=\{1,\ldots,m\}$. Give $(A,B)$ the weight $(-1)^{|A|}$. There are $2^{m-k}\binom mk$ distinct $(A,B)\in S$ with $|A|=k$ so the weighted count of elements of $S$ are $\sum_k(-1)^{k}\binom mk2^{m-k}$.

Now we have a sign-reversing almost-involution of $S$. Let $(A,B)\in S$ and $r$ be the largest entry of $A\cup B$ and define $(A',B')$ by moving $r$ from one set to the other. This defines a weight-reversing involution on $S-\{(\emptyset,\emptyset)\}$. This exceptional element $(\emptyset,\emptyset)$ has weight $1$.