Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are several identities that involve the sum of the product of binomial coefficients. However what I am searching for is an identity that involves the ratio of binomial coefficients. Specifically, I want to find a closed form expression for the sum $$\sum_{k=r-t}^n\frac{\binom{n}{k}}{\binom{k+t}{r}}, $$ where $n,r \in \mathbb{N}$ are fixed and $t$ is nonpositive and fixed.

Are there any standard formulae/identities that give this or are there methods for finding this sum?

I have restricted $t$ to be nonpositive, because the case where $t$ is positive is comparatively easier (in particular, $r=1, t=1$ is straight-forward to evaluate).

share|improve this question

migrated from cstheory.stackexchange.com Sep 1 '12 at 7:09

This question came from our site for theoretical computer scientists and researchers in related fields.

    
Mods, since I haven't even received a comment over the last two days, would it be ok to re-post this question now on MathOverflow? –  Ankur Aug 31 '12 at 17:46
    
Moderators are not checking all comments to all questions. If you have a question to moderators, it is more reliable to flag your own question, choose “it needs ♦ moderator attention,” and explains why it needs moderator attention. –  Tsuyoshi Ito Sep 1 '12 at 0:42
    
At least for me, this question is fairly uninteresting because it looks like just a random formula, and I fail to see why it is reasonable to expect that it has a nice closed-form expression (and also because I am not good at this kind of math). If you state why you are interested in this sum, some people may care more. –  Tsuyoshi Ito Sep 1 '12 at 0:43
    
Well, the motivation is hard to explain. It came up as an intermediate calculation. If its ok, can you help move it to math.SE? Otherwise I can merely repost it. –  Ankur Sep 1 '12 at 4:11
1  
Usually, if you have a ratio of binomial coefficients as the terms of a sum, a useful first step is to switch to hypergeometric form, and then do the manipulations on the resulting hypergeometric functions. –  J. M. Sep 1 '12 at 7:54

2 Answers 2

There is a technique known as Gosper's algorithm and another technique which is known as Zeilberger's algorithm. The two algorithms tackle these kinds of problems, if they succeed they will give a closed form formulas for the finite sum.

share|improve this answer

Take a look at Petkovsek and Wilf's book "A=B", they cover techniques for such hypergeometric sums in full detail. There are packages for their algorithms (which normally are much to messy for hand computation) for leading computer algebra packages.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.