Wednesday 25 June 2014

summation - Series with Double Binomial Coefficients



How do I show the following?




$$ \sum_{x=0}^{n} x {N_1 \choose {n-x}} {N_2 \choose x} = N_2 {N_1 + N_2 - 1 \choose n-1} $$



I tried breaking down the left hand side into factorials and pulling out $N_2$, but that did not help. How does one deal with these summmations in general?


Answer



$$
\binom{N_2}{x} = \frac{N_2}{x}\binom{N_2-1}{x-1}
$$



With this, the sum gets transformed to




$$
\sum_{x=1}^n x\binom{N_1}{n-x}\binom{N_2}{x} = N_2\sum_{x=1}^n\binom{N_1}{n-x}\binom{N_2-1}{x-1}.
$$



The rest is easy with a combinatorial argument. Starting the index with $0$ or $1$ doesn't make a difference.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...