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

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

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

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

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

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.

• 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
– luw
Apr 14 '19 at 17:45

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}.$$