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?

  • $\begingroup$ 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? $\endgroup$ – OR. Oct 16 '13 at 14:52
  • 1
    $\begingroup$ Nevermind, it does appear. $\endgroup$ – OR. Oct 16 '13 at 14:56
  • $\begingroup$ Yes, Gosper's algorithm shows it is true. $\endgroup$ – OR. Oct 16 '13 at 15:09
  • $\begingroup$ @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? $\endgroup$ – mathlove Oct 16 '13 at 15:24
  • $\begingroup$ 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]. $\endgroup$ – 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.

For the inductive step we need

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


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.