2
$\begingroup$

Let $0 < \ell \leq b \leq a$. Let $a > b+\ell$. I am trying to upper bound the following expression such that the upper bound evaluates to $\leq 1$ (clearly 1 is an upper bound but i want something nontrivial such that the upper bound is $<1$ whenever possible):

\begin{equation} \sum_{i=1}^{\ell} {\ell \choose i} \frac{{b \choose i}}{{a \choose i}} (-1)^{i+1} \end{equation}

In this process of trying it : the best thing i could do is do the following approximation: \begin{equation} \frac{{b \choose i}}{{a \choose i}} \approx (\frac{b}{a})^i \frac{e^{-1/b} e^{-2/b}....e^{-(i-1)/b}}{e^{-1/a} e^{-2/a}....e^{-(i-1)/a}} \end{equation} This leads to a summation of the form: \begin{equation} \sum_{i=1}^{\ell} {\ell \choose i} e^{-c_1{i^2}} c_2^i (-1)^{i+1} \end{equation} for some $c_1,c_2$

But i do not know whether this approximation will give an upper bound or not. I also do not know how to evaluate the approximate summation given above.

I am going to use my actual summation by multiplying with a number tending to infinity. So i need a very good approximation and it needs to be $<1$ whenever possible.

[Update]: I was able to reduce the summation to the following expression : Coefficient of $z^{\ell}$ in the following expression: \begin{equation} (1+z)^b \int_{0}^{1} (z-(z+1)x)^{\ell} (1-x)^{a-\ell} dx \end{equation} Any help with above integral is also appreciated...

Also the summation can be converted to: \begin{equation} \sum_{i=1}^{\ell} {\ell \choose i} {b \choose i} \frac{1}{(i-1)!} \sum_{j=0}^{i-1} \frac{{(i-1) \choose j}}{a-j} (-1)^{i-1-j}(-1)^{i+1} \end{equation}

$\endgroup$
0
$\begingroup$

The sum has a closed form so Stirling's asymptotic formula for the ratio of factorials should do the trick: $$\sum_{k=1}^n (-1)^{k+1} \binom{n}{k} \frac{ \binom{b}{k}}{\binom{a}{k}}= 1-\frac{\Gamma(-a)\Gamma(n+b-a)}{\Gamma(b-a)\Gamma(n-a)} $$ The identity is from a Gauss hypergeometric 2F1 evaluated at 1. Although it was not stated that $a,b$ could be integer, in those cases you would need to use reflection formulas to avoid an indeterminate expression.

$\endgroup$
  • $\begingroup$ Thanks a lot for a response. I searched for this formula.. It looks like you need a < b+n for this formula to hold. In my case a>b+n. Is there a closed form expression for a > b+n ? $\endgroup$ – Balaji sb Aug 28 '18 at 17:17
  • $\begingroup$ Works for $a>b+n$ too. The gamma function is finite for values where the argument is not a negative integer. Because there is a ratio, the times where one of the numerator gamma's goes infinite, so will a denominator one, and by using gamma function ID's and limits you can get something finite. It has to, because the left-hand side of the equation is finite. $\endgroup$ – skbmoore Aug 28 '18 at 18:43
  • $\begingroup$ Thanks a lot again for you response. sorry for troubling you again. I read the proof of the formula you gave from homepage.tudelft.nl/11r49/documents/wi4006/hyper.pdf . The proof seem to critically rely on the definition of gamma function in terms of integral $\int x^{z-1} e^{-x} dx$. Although i read that gamma function can be extended, its definition in terms of integral is valid only for positive values. The proof of the formula you gave depends on the definition in terms of integral. Can u clarify or give reference as to how to prove the formula you gave for negative values? $\endgroup$ – Balaji sb Aug 29 '18 at 5:35
  • $\begingroup$ Thanks a lot ...i proved the formula by induction... $\endgroup$ – Balaji sb Aug 30 '18 at 12:25
  • $\begingroup$ I proved the formula by induction assuming $\ell+1<b<a$ $\endgroup$ – Balaji sb Aug 30 '18 at 13:22

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.