Using sign-reversing involution to prove that $\sum^{n}_{k=p} (-1)^{k} \binom{n}{k} \binom{k}{p} = \delta_{n,p} (-1)^p$ for any $p \leq n$.

Question

My current progress is that I'm supposing $S$ to be $ \{ (A,B) | A \subset B \subset \{ 1, 2, ..., n \} ; n(A) = p \}$, and $sgn(A,B) = (-1)^{n(B)}$.

This gives

$$\sum_{(A,B) \in S} sgn(A,B) = \sum_{A \subset B \subset [n]} (-1)^{|B|}$$

$$ = \sum_{k} \sum_{B \in \binom{[n]}{k} } \sum_{A \in \binom{B}{k} } (-1)^k $$

$$ = \sum_{k} (-1)^k \binom{n}{k} \binom{k}{p}.$$

But I cannot define the involution $\iota$, could somebody please guide or give me some more hint to this question?

UPDATE : Now I can finally define $\iota ((A,B))$ as $(A, B \triangle \{ \alpha \} )$ for any abstract element $\alpha \in B$,

so it became $$sgn \iota ((A,B)) = sgn (A, B \triangle \{ \alpha \} )$$ $$= (-1)^{|B| - 1} $$ $$= - (-1)^{|B|} $$ $$ = - sgn ((A,B)) $$

Hence it is a sign-reversing involution.

But now I have got another problem. What is $Fix ( \iota )$ ?!

And I also lost how it became $(-1)^p \delta_{np}$.

RSVP if you have an idea or more hint. Thank you for your further information.

Answer 1

You are almost correct with the involution. What if $\alpha \in A$ and you take it out of $B$? Take then the smallest element that is not in $A$ to be the $\alpha$. Then the only way you can not do this is if everything is in $A$ which means $n=p$. If not everything is in $A$ as you point out, you can not fix anything.