Thread: 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?

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)

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.

...(1)

...(2)

Now compare (1) and (2).