Sunday, February 12, 2017

summation - 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?


Answer



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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...