1. ## Binomial Coefficient Proof

Prove that, for all real numbers r and all integers k and m,

C(r,m)C(m,k)=C(r,k)C(r-k,m-k)

Where C(r,m) is r choose m.

I'm terrible at these proofs because I never know which identity is needed to start.

Any help?

2. Easier to think of this through combinatorics.

Left hand side:
r = number of people
m= # of people being chosen for some committee from the group of r people.
k = Choosing k people out of the committee of m people for some special role (say senators).

Right hand side
Choosing k people who will be senators and in a committee. Then you designate the remaining empty committee spots (m-k) to the left over people (r-k)

3. Originally Posted by coolhandluke
Prove that, for all real numbers r and all integers k and m,

C(r,m)C(m,k)=C(r,k)C(r-k,m-k)

Where C(r,m) is r choose m.

I'm terrible at these proofs because I never know which identity is needed to start.

Any help?
An algebraic proof is also easy.

$\binom{r}{m} \binom{m}{k} = \frac{r!}{m!(r-m)!} \frac{m!}{k! (m-k)!}$ ...(1)

$\binom{r}{k} \binom{r-k}{m-k} = \frac{r!}{k! (r-k)!} \frac{(r-k)!}{(m-k)! (r-m)!}$ ...(2)

Now compare (1) and (2).