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...
Ans:
Solution:
First we note that
Let us change variables to make the summation more clearer,
If k-m=j, then
So we now get,
To get the last step I have used the identity
Here you are, then. Let's count the number of pairs of subsets such that A contains m elements.
Method 1. If B contains k elements (where m ≤ k ≤ n) then there are ways of choosing B. For each of these ways, there are ways of choosing A ⊆ B. Thus the total number of ways of choosing the pair {A, B} is .
Method 2. This time, choose A first. There are 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 ways of choosing B. Thus the total number of ways of choosing the pair {A, B} is .