Sum of product of two combinations

109 Views Asked by At

I have this

$$\displaystyle\sum_{i=1}^{a-1}\displaystyle\binom{a}{i}\displaystyle\binom{b-a}{a-i}$$

with $b>a$. I used Vandermonde's identity,

$$\displaystyle\sum_{i=0}^{r}\displaystyle\binom{m}{i}\displaystyle\binom{n}{r-i}=\displaystyle\binom{m+n}{r}$$

using $m=a$, $n=b-a$ and $r=a$ and found (correct me if i'm wrong)

$$\displaystyle\binom{b}{a}=\displaystyle\sum_{i=0}^{a}\displaystyle\binom{a}{i}\displaystyle\binom{b-a}{a-i} = \displaystyle\sum_{i=1}^{a-1}\displaystyle\binom{a}{i}\displaystyle\binom{b-a}{a-i}+\displaystyle\binom{b-a}{a}+\displaystyle\binom{a}{a}$$

Then, $$\displaystyle\binom{b}{a}-\displaystyle\binom{b-a}{a}-\displaystyle\binom{a}{a} =\displaystyle\sum_{i=1}^{a-1}\displaystyle\binom{a}{i}\displaystyle\binom{b-a}{a-i}$$

but i would like to know if there's any other form to write $\displaystyle\sum_{i=1}^{a-1}\displaystyle\binom{a}{i}\displaystyle\binom{b-a}{a-i}$ other than this one. Preferably with only one combination.

1

There are 1 best solutions below

2
On

$$S=\sum_{i=1}^{a-1} {a \choose i} {b-a \choose a-i}=\sum_{i=0}^{a} {a \choose i} {b-a \choose a-i}-1-{b-a \choose a}=S'-1-{b-a \choose a}$$ $$S'=\sum_{i=0}^{a} {a \choose i} {b-a \choose a-i}$$ $${b-a \choose a-i}= \text{Coefficient of}~ x^{a-i}~in~~~ (1+x)^{b-a}$$ Multiply by ${a \choose i}$ on both sides $${b-a \choose a-i}= \text{Coefficient of}~ x^{a-i}~~ in~~~ (1+x)^{b-a}$$ $${a \choose i}{b-a \choose a-i}= \text{Coefficient of}~ x^{a-i}~ in~~~ (1+x)^{b-a} {a \choose i}$$ Let us sum over $i$ on both sides: $$S'=\sum_{i=0}^{a}{a \choose i}{b-a \choose a-i}= \text{Coefficient of}~ x^{a}~ in~~~ \sum_{i=0}^{a}(1+x)^{b-a} {a \choose i} x^{-i}.$$ $$\implies S'=\text{Co-efficient of}~ x^a~ in (1+x)^{b-a}(1+\frac{1}{x})^a$$ $$\implies S'=\text{Co-efficient of}~ x^a~ in (1+x)^{b}={b \choose a}$$ Finally, $$S={b \choose a}-{b-a \choose a}-1$$