Applied Algebra (Prove the identity)?

[chredhat]

let m,n be positive integer. Prove the identity:

sum (i from 0 to k): { C(m, i) * C(n, k - i) } = C(m + n, k)

Hint: Consider the polynomial equation:

sum (k from 0 to m+n) {C(m + n, k) *z^k } = (1 + z)^(m+n) = ((1+z)^m) * ((1+z)^n)

I tried long time, still have no idea.

 

[Dick]

Express (1+z)^m and (1+z)^n as sums over powers of z using the binomial coefficients as they did in the hint for (1+z)^(m+n). Now equate equal powers of z on both sides.