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.

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

It's easy to see that $$ \sum_i {A\choose i} {B\choose n-i} = {A+B\choose n} $$ since when we choose $n$ things out of $A+B$, some ($i$ of them) are in the $A$ and the rest are in the $B$.

  • Is there any reasonable formula for $$ \sum_{i< I} {A\choose i} {B\choose n-i} = {A+B\choose n}, $$ i.e. we have a bound on how many of them are from the $A$ side?

  • Is the $B=1$ case any easier? (That being my real question.)

EDIT: I totally misasked this question, and have hopefully fixed it here: Partial sum over $M$, of ${m+j \choose M} {1-M \choose m+i-M}$?

share|cite|improve this question
Did you mean $B=1$ in the title? – PEV May 22 '11 at 14:52
For $B=1$, maybe you want to take a look at Pascal's rule. – Fabian May 22 '11 at 15:12
The formula holds for all integer $i$. (According to Knuth in Concrete Mathematics) – FUZxxl May 22 '11 at 15:24
In the first question, you didn't mean to include the right-hand side, did you? – Hans Lundmark May 22 '11 at 19:01

For B=1 this is rather easy:

${1 \choose j}$ is $1$ if $j$ is $0$ or $1$, and is $0$ for any other value of $j$. So your first expression becomes $ {A\choose n-1} {1\choose 1} + {A\choose n} {1\choose 0} = {A+1 \choose n} $ or as Fabian says, Pascal's rule

$$ {A\choose n-1} + {A\choose n} = {A+1 \choose n}. $$

Your second expression depends on $I$. If $I \le n-1$ then it gives a sum of 0; if $I = n$ and $i \lt I$ it give a sum of ${A\choose n-1}$, and if $I \gt n$ it gives a sum of ${A+1 \choose n}$.

share|cite|improve this answer

Your Answer


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.