Proving Binomial Identities: Sigma of k = 0 to m

[bodensee9]

hello,

i am supposed to show that

Sigma of k = 0 to m, (n, k) (n - k, m - k) = 2^m (n, m)

So I have after expanding:

(n, k) = n!/(n-k)!k! and (n-k, m-k) = (n-k)!/(m-k)!(n-m)!
so together the (n-k)! cancels out and I have
n!/k!(m-k)!(n-m)!
and that is
n!/m!(n-m)! which is
(n, m)

so then I can take (n, m) out of the sigma and then I would have
(n, m)*Sigma from k = 0 to m 1, but then how do I get the 2^m?

Thanks.

 

[Dick]

You seem to think that 1/(k!*(m-k)!) is 1/m!. It's not. Try some numerical examples. On the other hand it's easy to find the sum of that quantity over k. You probably proved sum over k of (m,k)=2^m, didn't you?

 

[bodensee9]

Oh right. Thanks!

Yes, it's equal to (1 + 1) ^ m , so that is 2^m.