1. ## binomial

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).

2. Originally Posted by vivian
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...

$\boxed{\sum_{k=m}^n {{k \choose m}\cdot {n \choose k}} = ??}$

Ans: $2^{n-m} \cdot {n \choose m}$

Solution:

First we note that ${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
$\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,

$\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 $\sum_{j=0}^n{n \choose j} = 2^n$

3. Originally Posted by Isomorphism
I hope someone comes with a proof by double counting. I want to see one
I hate combinations proof through algebra.
Here you are, then. Let's count the number of pairs of subsets $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 $\textstyle{n\choose k}$ ways of choosing B. For each of these ways, there are $\textstyle{k\choose m}$ ways of choosing A ⊆ B. Thus the total number of ways of choosing the pair {A, B} is $\sum_{k=m}^n {{k \choose m}\cdot {n \choose k}}$.

Method 2. This time, choose A first. There are $\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 $2^{n-m}$ ways of choosing B. Thus the total number of ways of choosing the pair {A, B} is ${n \choose m} \cdot 2^{n-m}$.

4. Thanks Opalg.
At first I thought this post is suspiciously related to vivian's other post.
But then I think this was a substep in the other question because if we let m vary from 0 to n, then we get $3^n$ solutions.