0
$\begingroup$

How to calculate $$\sum\limits_{k=0}^{m-n} {m-k-1 \choose n-1} {k+n \choose n}.$$

$\endgroup$
1
  • $\begingroup$ Mathematica finds $$\frac{\Gamma (m) \, _2F_1(n+1,n-m;1-m;1)}{\Gamma (n) \Gamma (m-n+1)} $$ for this sum. $\endgroup$
    – user64494
    Apr 15 '19 at 2:57
10
$\begingroup$

An easy combinatorial way to see that $$\sum_{k=0}^{m-n}\binom{m-k-1}{n-1}\binom{k+n}n=\binom{m+n}{2n}:$$

The right hand side is the number of ways to pick a subset of size $2n$ from $\{1,2,\dots,m+n\}$.

The $k$ term on the left hand side is the number of ways to pick a subset of size $2n$ from $\{1,2,\dots,m+n\}$ whose $n$th element is $m-k$.

$\endgroup$
2
  • 3
    $\begingroup$ I cheated, of course, and reverse engineered the formula from T. Amdeberhan’s answer. $\endgroup$ Apr 14 '19 at 18:29
  • $\begingroup$ It's still a very nice combinatorial interpretation! @Jeremy Rickard $\endgroup$
    – luw
    Apr 14 '19 at 19:59
5
$\begingroup$

This is the evaluation: $$\sum_{k=0}^{m-n}\binom{m-k-1}{n-1}\binom{k+n}n=\binom{m+n}{2n}.$$ There might be a direct connection to Vandermonde's identity but let's apply the so-called Wilf-Zeilberger technique. To this end, divide through by the RHS and define the functions $$F(m,k)=\frac{\binom{m-k-1}{n-1}\binom{k+n}n}{\binom{m+n}{2n}} \qquad \text{and} \qquad G(m,k)=\frac{F(m,k)\cdot(m-n)!(m-k)k}{(-m+k+n-1)(m+n+1)}.$$ Then, check routinely that (for instance, divide through by $F(m,k)$ on both sides) $$F(m+1,k)-F(m,k)=G(m,k+1)-G(m,k).$$ Now, sum both sides over all integers $k$ and notice that the RHS vanishes. That means $h(m+1)-h(m)=0$ where $h(m)=\sum_kF(m,k)$. It remains to check that $h(n)=1$ which implies $h(m)=1$ for all $m$. This completes the proof.

$\endgroup$
1
  • $\begingroup$ Thank you! Could you give me some hint how to simplify it? I guess there might be some relation with Vandermonde's Identity. But I cannot connect them clearly. @T. Amdeberhan $\endgroup$
    – luw
    Apr 14 '19 at 17:45
3
$\begingroup$

Yes, it is Chu -- Vandermonde identity. We have ${m-k-1\choose n-1}={m-k-1\choose m-n-k}=(-1)^{m-n-k}{-n\choose m-n-k}$, ${k+n\choose n}={k+n\choose k}=(-1)^k{-n-1\choose k}$. Thus your sum equals $$ (-1)^{m-n}\sum_{k=0}^{m-n} {-n\choose m-n-k}{-n-1\choose k}= (-1)^{m-n}{-2n-1\choose m-n}={m+n\choose m-n}. $$

$\endgroup$

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.