0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – pizet Nov 1 '18 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.