Proving Permutation Identity: Ʃ(n choose k)(m-n choose n-k) = (m choose n)

[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?

 

[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 ?

 

[mfb]

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 ;).

 

[tiny-tim]

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

hi mfb!

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

 

[Ray Vickson]

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?

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