# Binomial Coefficient Identities

I am trying to simplify the following fraction, which I think is equal to 1 but I am not sure. $$\frac{\frac{\left(\begin{array}{c} b-1\\ k-1 \end{array}\right)\left(\begin{array}{c} r\\ n-k \end{array}\right)}{\left(\begin{array}{c} r+b-1\\ n-1 \end{array}\right)}}{\frac{\left(\begin{array}{c} b\\ k \end{array}\right)\left(\begin{array}{c} r\\ n-k \end{array}\right)}{\left(\begin{array}{c} r+b\\ n \end{array}\right)}}$$ I tried to use the identity $$\left(\begin{array}{c} n\\ r \end{array}\right)=\left(\begin{array}{c} n-1\\ r-1 \end{array}\right)+\left(\begin{array}{c} n-1\\ r \end{array}\right)$$ I have done the following

Step 1: $$\frac{\left(\begin{array}{c} b-1\\ k-1 \end{array}\right)\left(\begin{array}{c} r\\ n-k \end{array}\right)}{\left(\begin{array}{c} r+b-1\\ n-1 \end{array}\right)}\cdot\frac{\left(\begin{array}{c} r+b\\ n \end{array}\right)}{\left(\begin{array}{c} b\\ k \end{array}\right)\left(\begin{array}{c} r\\ n-k \end{array}\right)}$$

Step 2: $$\frac{\left(\begin{array}{c} b-1\\ k-1 \end{array}\right)}{\left(\begin{array}{c} b\\ k \end{array}\right)}\cdot\frac{\left(\begin{array}{c} r+b\\ n \end{array}\right)}{\left(\begin{array}{c} r+b-1\\ n-1 \end{array}\right)}$$

From there I get stuck here

$$\frac{\left[\left(\begin{array}{c} b\\ k \end{array}\right)-\left(\begin{array}{c} b-1\\ k \end{array}\right)\right]}{\left(\begin{array}{c} b\\ k \end{array}\right)}\cdot\frac{\left(\begin{array}{c} r+b\\ n \end{array}\right)}{\left[\left(\begin{array}{c} r+b\\ n \end{array}\right)-\left(\begin{array}{c} r+b-1\\ n \end{array}\right)\right]}$$

Is there any other identity that would be more useful for this problem? If not does anyone have a useful hint for where to proceed from here?

• Express the binomial coefficients in terms of factorials. There should be a lot of cancellation. Recall that $\binom{b}{a}=\frac{b!}{a!(b-a)!}$. – André Nicolas Sep 26 '13 at 1:37
• @AndréNicolas So, there are no other tricks? I will try the factorials now. – JimmyJackson Sep 26 '13 at 1:39
• There are endlessly many ideas one could bring to bear. But the one I mentioned will be useful. – André Nicolas Sep 26 '13 at 1:42
• @AndréNicolas I think I will go back to step two, and then express it as factorial. I think that using the identity above will only make cancellation more difficult. – JimmyJackson Sep 26 '13 at 1:45
• I maybe should have said, but didn't: don't use the identity you started to use. – André Nicolas Sep 26 '13 at 1:56

If we use the identity $\displaystyle\binom{m}{n}=\frac{m}{n}\binom{m-1}{n-1}$, we obtain

$$\displaystyle\frac{\binom{b-1}{k-1}\binom{r+b}{n}}{\binom{b}{k}\binom{r+b-1}{n-1}}=\frac{\binom{b-1}{k-1}\frac{r+b}{n}\binom{r+b-1}{n-1}}{\frac{b}{k}\binom{b-1}{k-1}\binom{r+b-1}{n-1}}=\frac{k}{b}\cdot\frac{r+b}{n}$$

• That is a much nicer way of dealing with this mess! – JimmyJackson Sep 28 '13 at 23:33

The Fraction above does not simplify down to 1 as I had thought it would. It simplifies down to $\frac{k}{b}\cdot\frac{r+b}{n}$.

If we go back to Step 2 of the original question, we have

$$\frac{\left(\begin{array}{c} b-1\\ k-1 \end{array}\right)}{\left(\begin{array}{c} b\\ k \end{array}\right)}\cdot\frac{\left(\begin{array}{c} r+b\\ n \end{array}\right)}{\left(\begin{array}{c} r+b-1\\ n-1 \end{array}\right)}$$

Now, we can express the binomial coefficients as factorials, as suggest by André Nicolas above, and then we get $$\frac{\left(\frac{(b-1)!}{[(b-1)-(k-1)]!(k-1)!}\right)}{\left(\frac{b!}{(b-k)!k!}\right)}\cdot\frac{\left(\frac{(r+b)!}{(r+b-n)!n!}\right)}{\left(\frac{(r+b-1)!}{[(r+b-1)-(n-1)](n-1)!}\right)}$$ Which simplifies to $$\frac{\left(\frac{(b-1)!}{(b-k)!(k-1)!}\right)}{\left(\frac{b!}{(b-k)!k!}\right)}\cdot\frac{\left(\frac{(r+b)!}{(r+b-n)!n!}\right)}{\left(\frac{(r+b-1)!}{(r+b-n)!(n-1)!}\right)}$$ Which in turn simplifies to $$\frac{\left(\frac{(b-1)!}{(k-1)!}\right)}{\left(\frac{b!}{k!}\right)}\cdot\frac{\left(\frac{(r+b)!}{n!}\right)}{\left(\frac{(r+b-1)!}{(n-1)!}\right)}$$ Which is equal to $$\left(\frac{(b-1)!k!}{(k-1)!b!}\right)\left(\frac{(r+b)!(n-1)!}{n!(r+b-1)!}\right)$$ Which at last reduces down to $$\frac{k}{b}\cdot\frac{r+b}{n}$$

If you know of any other clever ways to simplify this, please post you answer. Thanks.