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