Combinatorial proof for $\sum_{k=0}^p (-1)^k {n \choose k} = (-1)^p {n-1 \choose p}$ [duplicate]

Question

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.

Answer 1

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$.