4
$\begingroup$

I am trying to give a combinatorial proof for: $$\sum_{k=0}^p (-1)^k {n \choose k} = (-1)^p {n-1 \choose p}$$ Where $p$ and $n$ are natural numbers.

We could easily see that if $p=n$ this reduces to the fact that a set has as many subsets of even cardinality, as those with odd cardinality. However, this formula suggests a relation between the even and odd cardinalities less that $p$.

Note: I'm not interested in an algebraic proof, as Pascal's identity gives a telescopic sum on the RHS.

Thank you in advance.

$\endgroup$

marked as duplicate by Sil, Mike Earnest, Austin Mohr, Misha Lavrov, Paul Frost Apr 26 at 21:53

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\begingroup$

The LHS counts subsets of $\{1,2,\dots,n\}$ whose size is at most $p$, with even subsets counted positively and odd subsets counted negatively.

We define a sign reversing involution of such subsets; if $1$ is in the subset, remove it, otherwise, add it in. This involution partitions almost all of the subsets of size at most $p$ into pairs which cancel each other in the sum.

The only unpaired subsets are those with size exactly $p$ which do not contain $1$, as adding $1$ would make a subset of size $p+1$. The number of such subsets is $\binom{n-1}p$, and they are counted with sign $(-1)^p$.

$\endgroup$
  • $\begingroup$ I just don't understand what does it mean for the involution itself to be sign-reversing? $\endgroup$ – FuzzyPixelz Apr 23 at 20:14
  • $\begingroup$ @FuzzyPixelz it means it takes even subsets to odd subsets, and vice versa. $\endgroup$ – Mike Earnest Apr 23 at 20:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.