I have two questions to prove using PIE.
#9. Use PIE to prove the following identities:
(a) $\sum_{i=0}^n(-1)^i{n\choose i}{m+n-i\choose k-i}={m\choose k}$
(b) $\sum_{r=0}^n(-1)^{n-r}{n \choose r}r^n=n!$
For a, I thought that I should choose k among m from RHS, but on LHS, I don't know how to consider $i$ elements chosen from n first.
For b, I really don't have any idea to understand LHS. Please help me.
On
For (b), imagine having $n$ boxes to colour in $n$ distinct colours. The right hand side is the number of ways of colouring the boxes so each colour appears exactly once. It is easier to analyse the sum on the LHS from $r=n$ downwards. The number of ways of colouring each box in any colour is $n^n$. Then subtract all those colourings which don't use colour 1: $(n-1)^n$ of them; but you also need to subtract those that don't include colour 2, 3, ..., so subtract $(n-1)^n \times {n \choose 1}$. But then (PIE) you have double-subtracted, so need to add back, the colourings that exclude both colours 1 and 2, 2 and 3 etc: there are $(n-2)^n \times {n \choose 2}$ of these. Continue in this way with the remaining terms of the PIE to get the LHS.
For (a), imagine $m$ blue balls and $n$ red ones in an urn. Select $k$ balls. Then the number of ways of getting all $k$ blue is $m\choose k$. The left hand side is $$\mbox{number of ways of getting any }k\mbox{ from } n+m = {m+ n\choose k}$$ $$- \big(\mbox{number of ways with red ball 1 in the selection} + \mbox{number of ways with red ball 2 in the selection} + ...\big) = {m+ n-1\choose k} \times {n\choose 1}$$ $$+ \big(\mbox{number of ways with red balls 1 and 2 in the selection} + \mbox{number of ways with red balls 1 and 3 in the selection} + ...\big) = {m+ n-2\choose k} \times {n\choose 2}$$ and so on.