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

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.

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

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