Wednesday, 14 May 2014

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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...