# Proof of combinatorial identity

I need a edit:combinatorial proof of the following identity:

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

I know that I should use inclusion-exclusion, but I am getting stuck.

Thanks!

Hint: Try to expand $(2+(-1))^n$.

• But that's not a "combinatorial" proof in the sense probably intended. – Michael Hardy Nov 20 '13 at 21:22

Hints:

\begin{align*}\binom nk=\binom n{n-k}\;,\;\;0\le k\le n\\{}\\ (a+b)^n=\sum_{k=0}^n\binom nka^kb^{n-k}\;,\;\;\forall\,a,b\in\Bbb R\end{align*}

• But this seems more algebraic than combinatorial. The question emphasized that the proof is to be "combinatorial". – Michael Hardy Nov 20 '13 at 21:23
• Yes, now it says, after the OP edited his original question, which didn't ask for a "combinatorial proof". You re-edited that editing, @MichaelHardy . Sometimes it's worth to go back to the original, in particular if already there are some answers... – DonAntonio Nov 20 '13 at 23:57

If you are interested in inclusion exclusion try this. Our universe will be $01$ strings of length $n$. We will double count the number of ways to get all $0$. The LHS is clear there is only one way to do this. For the RHS, let $A_{i}$ be the event that the $i^{th}$ spot has a $1$ in it. This should set you up for PIE. So we should have

$$1=\sum_{S\subset[n]}(-1)^{|S|}\left|\bigcap_{i\in S}A_{i}\right|$$

I leave it to you to compute $\left|\bigcap_{i\in S}A_{i}\right|$. But I think the binomial theorem is much easier as shown in the other answers.