1708Thanks Shubhodip Nice Solution
can we solve Using Binomial
\hspace{-16}$Prove that::\\\\\\ $\mathbf{\binom{n}{0}\binom{n}{k}+\binom{n}{1}\binom{n-1}{k-1}+...........+\binom{n}{k}\binom{n-k}{0}=2^k.\binom{n}{k}}$\\\\\\ Where $\mathbf{n\;,k\in\mathbb{N}\;,0\leq k\leq n}$
-
UP 0 DOWN 0 0 2
2 Answers
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}