Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does anybody know of any techniques to solve the following sum (or a fast way (polynomial in N) to compute it):

$$\sum_{i=0}^{N} \binom{N-i}{A} \cdot \binom{\lfloor iP/Q \rfloor + 1}{B}$$

where $P$ and $Q$ are relatively prime positive integers, and $A$,$B$ are positive integers.

When $P = Q = 1$, the solution can be found in Concrete Mathematics, and it's $\binom{N+2}{A+B+1}$. I suspect it's also possible to find a closed form when $Q = 1$, and $P > 1$, but I haven't found it. I'm interested in the general solution, though.

share|cite|improve this question

Your Answer


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