21Consider a set A with n elements.
And consider the set S= \left \{ \left ( P \right ) ,\left ( T \right )\right \} : P\subseteq A,\; |P|= k , \; \; T \subseteq P,\; 0\leq |T|\leq k
P can be chosen in \binom{n}{k} ways, and T can be choosen in 2^k ways.
so easy to see that |S|= 2^k \binom{n}{k}
We will count |S| in another way.
If |T|= r,\; 0\leq r\leq k, Then elements of T can be chosen in \binom{n}{r} ways. P must contain the elements of T, since T\subseteq P , plus it must contain k-r elements from the set A-T, which can happen in \binom{n-r}{k-r} ways. So |S|= \sum_{r=0}^{k}\binom{n}{r}\binom{n-r}{k-r}.
We have proved \sum_{r=0}^{k}\binom{n}{k}\binom{n-r}{k-r} = 2^k \binom{n}{k}
