# Is this equation about binomial-coefficients true?

Question : Is the following true?

$$\sum_{r=k}^{n}\frac{\binom{q}{r}}{\binom{p}{r}}=\frac{p+1}{p-q+1}\left(\frac{\binom{q}{k}}{\binom{p+1}{k}}-\frac{\binom{q}{n+1}}{\binom{p+1}{n+1}}\right)$$ for $p\ge q\ge n\ge k\in\mathbb N$.

Motivation : I've known the following : $$\sum_{r=1}^{n}\frac{\binom{n}{r}}{\binom{n+m}{r}}=\frac{n}{m+1}.$$ This is the case of $(p,q,k)=(n+m,n,1)$. Then, I reached the above expectation. However, I can neither prove that this expectation is true nor find any counterexample. Can anyone help?

• The left hand side is a polynomial in $q$, but isn't it the right hand side rational, with a pole at $q=p+1$? I don't see the factor $p-q+1$ appearing in the numerator of the right hand side. Does it? – OR. Oct 16 '13 at 14:52
• Nevermind, it does appear. – OR. Oct 16 '13 at 14:56
• Yes, Gosper's algorithm shows it is true. – OR. Oct 16 '13 at 15:09
• @ABC: Thanks. I saw wiki about Gosper's algorithm, but I can't understand it well. Do you know the other helpful pages which have the proof? – mathlove Oct 16 '13 at 15:24
• Gosper's algorithm is implemented in many computer programs. It is in Mathematica, or in Wolframalpha. You can read about it in the book A=B that is free to download here [math.upenn.edu/~wilf/Downld.html]. – OR. Oct 16 '13 at 15:53

The identity can be proved in a routine way by induction on $n$. This is not true of your motivating identity, so this seems to be a nice example where a more general problem is actually easier to solve.
$$\frac{\binom{q}{n+1}}{\binom{p}{n+1}} = - \frac{p+1}{p-q+1} \left( \frac{\binom{q}{n+2}}{\binom{p+1}{n+2}} - \frac{\binom{q}{n+1}}{\binom{p+1}{n+1}} \right)$$
for $p \ge q > n \ge k$. Rewriting three binomial coefficients using the identities $\binom{q}{n+2} = \binom{q}{n+1}\frac{q-n-1}{n+2}$, $\binom{p}{n+1} = \binom{p+1}{n+1}\frac{p-n}{p+1}$ and $\binom{p+1}{n+2} = \binom{p+1}{n+1}\frac{p-n}{n+2}$ and then taking out $\binom{q}{n+1}/\binom{p+1}{n+1}$, this is equivalent to
$$\frac{p+1}{p-n} = - \frac{p+1}{p-q+1} \left( \frac{\frac{q-n-1}{n+2}}{\frac{p-n}{n+2}} - \frac{1}{1} \right)$$
which is easily verified. The base case of the induction when $n=k$ can be checked by similar methods.