# Combinatorial proofs of several binomial sums

I would like to ask if you know of any combinatorial (double counting) arguments for finding a closed formula for the following sums:

1. $$\sum_{k=m}^n{k\choose m}{n\choose k}$$, where $${n\choose k} = 0$$ for $$n < k$$.
2. $$\sum_{k=1}^n {k\choose m}\frac{1}{k}$$.
3. $$\sum_{k=0}^n {k\choose m}k$$.

Thank you for any ideas.

1)

$$\sum_{k=m}^n\binom{k}{m}\binom{n}{k}=\binom{n}{m}\sum_{k=m}^n\binom{n-m}{k-m}=\binom{n}{m}\sum_{k=0}^{n-m}\binom{n-m}{k}=\binom{n}{m}2^{n-m}$$

2)

$$\sum_{k=1}^n\binom{k}{m}\frac1k=\frac1m\sum_{k=1}^n\binom{k-1}{m-1}$$

3)

$$\sum_{k=0}^n\binom{k}{m}k=(m+1)\sum_{k=1}^n\binom{k+1}{m+1}-\sum_{k=0}^n\binom{k}{m}$$

Now apply hockeystick identity to find closed forms for 2) and 3).

• Yes, but can you give a combinatorial argument? In a particular a double counting arugment, where you show that both sides of the identity count the same thing? – pizet Nov 1 '18 at 10:14