For natural numbers m<=n calculate (i.e. express by a simple formula not containing a sum) sigma (k=m) to (n) (k choose m) (n choose k).
I hope someone comes with a proof by double counting. I want to see one
I hate combinations proof through algebra.
But well...
$\displaystyle \boxed{\sum_{k=m}^n {{k \choose m}\cdot {n \choose k}} = ??}$
Ans:$\displaystyle 2^{n-m} \cdot {n \choose m}$
Solution:
First we note that $\displaystyle {k \choose m}\cdot {n \choose k} = {n \choose m}\cdot {{n-m} \choose {k-m}}$
Let us change variables to make the summation more clearer,
If k-m=j, then
$\displaystyle \sum_{k=m}^n {{k \choose m}\cdot {n \choose k}} = \sum_{j=0}^{j = n-m} {n \choose m}\cdot {{n-m} \choose j} $
So we now get,
$\displaystyle \sum_{k=m}^n {{k \choose m}\cdot {n \choose k}} = {n \choose m}\cdot {\sum_{j=0}^{n-m}{{n-m} \choose j}} = {n \choose m} \cdot 2^{n-m}$
To get the last step I have used the identity $\displaystyle \sum_{j=0}^n{n \choose j} = 2^n$
Here you are, then. Let's count the number of pairs of subsets $\displaystyle A\subseteq B\subseteq\{1,2,3,\ldots,n\}$ such that A contains m elements.
Method 1. If B contains k elements (where m ≤ k ≤ n) then there are $\displaystyle \textstyle{n\choose k}$ ways of choosing B. For each of these ways, there are $\displaystyle \textstyle{k\choose m}$ ways of choosing A ⊆ B. Thus the total number of ways of choosing the pair {A, B} is $\displaystyle \sum_{k=m}^n {{k \choose m}\cdot {n \choose k}}$.
Method 2. This time, choose A first. There are $\displaystyle \textstyle{n\choose m}$ ways of doing this. For each such A, there are n–m elements not in A. Each of these elements has two possibilities: either it is in B or it is not in B (of course, B also contains all the elements of A). That gives $\displaystyle 2^{n-m}$ ways of choosing B. Thus the total number of ways of choosing the pair {A, B} is $\displaystyle {n \choose m} \cdot 2^{n-m}$.