My goal is to show :
$$\sum_{i=0}^{m} {n \choose i} {n - i \choose m - i} = {n \choose m} 2^m $$ where $$0 \leq m \leq n$$ I have algebraically proved that but I was wondering if there is a combinatorial argument for this proof. Thank you
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Your equation makes no sense: $i$ is a dummy variable with no fixed value on the lefthand side and a fixed constant of some kind on the righthand side. $\endgroup$– Brian M. ScottCommented Oct 4, 2020 at 16:51
-
1$\begingroup$ That $i$ on RHS should probably be $m$. $\endgroup$– player3236Commented Oct 4, 2020 at 16:52
-
1$\begingroup$ I am sorry there was a typo. I fixed it $\endgroup$– foobarCommented Oct 4, 2020 at 16:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
There are two ways to count the number of subsets $A,B\subset\{1,\ldots,n\}$ with $A\subset B$ and $|B|=m$:
On the left you pick any subset $A$ of at most $m$ elements, and then extend it to a subset $B$ of $m$ elements. On the right you pick a subset $B$ of $m$ elements, and then pick any subset $A$ of $B$.