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

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?

• If you use binomial theorem, the right side is just $2^m(1-\frac 12)^m$. – Yu Ding Nov 14 '18 at 18:10

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