4
$\begingroup$

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}$?

  • 0
    Did you mean $B=1$ in the title?2011-05-22
  • 2
    For $B=1$, maybe you want to take a look at [Pascal's rule](http://en.wikipedia.org/wiki/Pascal%27s_rule).2011-05-22
  • 0
    The formula holds for all integer $i$. (According to Knuth in *Concrete Mathematics*)2011-05-22
  • 0
    In the first question, you didn't mean to include the right-hand side, did you?2011-05-22

1 Answers 1