# Homework Help: Permutation Proof

1. Jun 27, 2013

### Brandon1994

1. Prove the following identity:
Ʃ(n choose k)(m-n choose n-k) = (m choose n)
from k = 0 to k = n

I've tried induction, and just played around with a few properties of permutations, but nothing seems to satisfy the proof, any ideas?

2. Jun 27, 2013

### tiny-tim

Hi Brandon1994!

If you choose n things from m,

how many of those n will be in the first n, and how many will be in the last n-m ?

3. Jun 27, 2013

### Staff: Mentor

I would use a direct approach: Show that the left side is the number of ways to choose n elements out of a set of m elements. The sum is very intuitive if you see what it does.

Edit: tiny-tim, don't make it too easy ;).

4. Jun 27, 2013

### tiny-tim

hi mfb!

i assumed he'd already tried to split the sum, and needed an extra hint

5. Jun 27, 2013

### Ray Vickson

Hint: (n choose k) is called the binomial coefficient for a good reason: it appears in the binomial expansion! Exploit that fact.