# Combinatorial Proof for the Identity $\sum_{k=0}^n \binom{n}{k}\left(-2\right)^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!

• $(1-2)^n$. Binomial theorem. – hmakholm left over Monica Dec 8 '15 at 18:03
• @HenningMakholm, the questions asks for a combinatorial proof. The algebraic proof is trivial. – learner Dec 8 '15 at 18:05
• @HenningMakholm Wow that is way easier than what I had in mind when I was proving it algebraically. I hate induction (I think it's takes the fun out of proving things) and I was doing it by induction ... – terrace Dec 8 '15 at 18:21

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.

• Thank you for a very cool approach to the problem! Maybe the algebraic way is easier after all - I was doing it by induction which I find to be extremely boring/uninteresting as a proof technique, I did not realize it was possible to simply expand $(1-2)^n$ as Henning Makholm pointed out. – terrace Dec 8 '15 at 18:20
• @Terrence: You’re welcome! – Brian M. Scott Dec 8 '15 at 18:27