1
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ $(1-2)^n$. Binomial theorem. $\endgroup$ – Henning Makholm Dec 8 '15 at 18:03
  • $\begingroup$ @HenningMakholm, the questions asks for a combinatorial proof. The algebraic proof is trivial. $\endgroup$ – learner Dec 8 '15 at 18:05
  • $\begingroup$ @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 ... $\endgroup$ – terrace Dec 8 '15 at 18:21
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – terrace Dec 8 '15 at 18:20
  • $\begingroup$ @Terrence: You’re welcome! $\endgroup$ – Brian M. Scott Dec 8 '15 at 18:27

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.