# Combinatorial proof of $1=\sum_{i=0}^n{(-1)^i \binom{n}{i} 2^{n-i}}$

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.

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

## 1 Answer

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

• Why is the number of subsets containing $0$ elements equal to $\sum\limits_{S \subseteq [n]} (-1)^{|S|} f_S$? – NightRa Nov 6 '15 at 16:22
• The Principle of Inclusion-Exclusion tells us that. – Marcus M Nov 6 '15 at 18:24
• 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? – NightRa Nov 6 '15 at 19:06
• @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 – Marcus M Nov 6 '15 at 19:10