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

1 Answer 1

10
$\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$
2
  • 1
    $\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
    Commented Dec 8, 2015 at 18:20
  • $\begingroup$ @Terrence: You’re welcome! $\endgroup$ Commented Dec 8, 2015 at 18:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .