combinatorics - Combinatorial Proof for the Identity $sum_{k=0}^n binom{n}{k}left(-2right)^k = (-1)^n$

I know how to prove this identity algebraically, but that's the stupidly boring way of doing problems. I can't think of a combinatorial proof for this, as in using counting committees or something like that. It's hard to deal with the negative $2$ ...

$$\displaystyle\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n$$

Any help is appreciated, thanks!

Answer

The most natural combinatorial proof starts by multiplying the desired identity by $(-1)^n$ to make it

$$\sum_{k=0}^n\binom{n}k2^k(-1)^{n-k}=1\;.$$

Of course this is immediate from the binomial theorem, but if you want something more explicitly combinatorial, you can then replace $k$ by $n-k$ to get

$$\sum_{k=0}^n\binom{n}k(-1)^k2^{n-k}=1\;.$$

Suppose that we want to count the subsets of $[n]=\{1,\ldots,n\}$ that do not contain any element of $[n]$. Of course the only such subset is $\varnothing$, so the value should be $1$. On the other hand, if for $k\in[n]$ we let $\mathscr{A}_k$ be the family of subsets of $[n]$ containing $k$, then for any non-empty $F\subseteq[n]$ we have

$$\left|\bigcap_{k\in F}\mathscr{A}_k\right|=2^{n-k}\;,$$

and there are $\binom{n}k$ such $F\subseteq[n]$, so the result follows from the inclusion-exclusion principle.