# Partial sum of ${A \choose i} {B\choose n-i}$, when $B=-1$?

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

-
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

${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}$.