3
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ But this seems more algebraic than combinatorial. The question emphasized that the proof is to be "combinatorial". $\endgroup$ – Michael Hardy Nov 20 '13 at 21:23
  • $\begingroup$ 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... $\endgroup$ – DonAntonio Nov 20 '13 at 23:57
2
$\begingroup$

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.

$\endgroup$

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.