1
$\begingroup$

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?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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