# 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

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