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.
No comments:
Post a Comment