1
$\begingroup$

I'm searching for a combinatorial proof of the following equality:
$$1=\sum_{i=0}^n{(-1)^i \binom{n}{i} 2^{n-i}}$$ It's trivial to show using Newton's binomial theorem: $(-1+2)^n=1$, but I'm interested in a direct combinatorial explanation of this fact, without any simplifications.

I see the term ${\binom{n}{i} 2^{n-i}}$ as an ordered pair of a subset of size $i$ (from a set of size $n$) and a subset of varying length of the remaining elements in the set, but the orderdness and the $(-1)^i$ got me stuck in this line of thought.

$\endgroup$
  • 1
    $\begingroup$ Do you mean $(-1)^i $? $\endgroup$ – Marcus M Nov 6 '15 at 14:19
  • $\begingroup$ @MarcusM Indeed. Fixed. $\endgroup$ – NightRa Nov 6 '15 at 14:39
4
$\begingroup$

We can prove this using the Principle of Inclusion Exclusion. For each subset $S \subset [n]$, let $f_S$ be the number of subsets of $[n]$ that contain $S$. Then note that $f_S = 2^{n - |S|}$. The principle of inclusion exclusion then tells us that the number of subsets containing precisely $0$ elements is $$ \sum\limits_{S \subseteq [n]} (-1)^{|S|} f_S = \sum\limits_{i = 0}^n \sum\limits_{\substack{S \subseteq [n]\\ |S| = i}} (-1)^i 2^{n - i} = \sum\limits_{i = 0}^n (-1)^i \binom{n}{i} 2^{n-i}.$$

However, since there is only one set with $0$ elements---namely the empty set---this quantity must be equal to $1$.

$\endgroup$
  • $\begingroup$ Why is the number of subsets containing $0$ elements equal to $\sum\limits_{S \subseteq [n]} (-1)^{|S|} f_S$? $\endgroup$ – NightRa Nov 6 '15 at 16:22
  • $\begingroup$ The Principle of Inclusion-Exclusion tells us that. $\endgroup$ – Marcus M Nov 6 '15 at 18:24
  • $\begingroup$ I mean, what are the sets AiAi we are applying the Inclusion-Exlusion principle to? How are the subsets containing precisely 0 elements are the union of them while fSfS are their intersection? $\endgroup$ – NightRa Nov 6 '15 at 19:06
  • $\begingroup$ @NightRa, In combinatorics, there is a much generalized version of inclusion-exclusion that isn't just for counting the cardinality of unions. I'd rather not develop the whole theory here; it's the core of Chapter 2 of Stanley's Enumerative Combinatorics Vol. 1, which is available online here: math.mit.edu/~rstan/ec/ec1 $\endgroup$ – Marcus M Nov 6 '15 at 19:10

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.