Proof of combinatorial identity

Question

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!

Answer 1

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

Answer 2

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*}$$

Answer 3

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.