Prove equality between binomial coefficients.

Question

Using the Binomial theorem, prove that: $$ \binom{m+n}{k}=\sum_{j=0}^k \binom{n}{j}\binom{m}{k-j},\; 0\leq k\leq m+n$$

Answer 1

HINT :

$$(1+x)^n=\binom n0+\binom n1x+\cdots +\binom{n}{n-1}x^{n-1}+\binom nnx^n$$ $$(1+x)^m=\binom m0+\binom m1x+\cdots +\binom{m}{m-1}x^{m-1}+\binom mmx^m$$

Now consider the coefficient of $x^k$ in the expansion of $(1+x)^n(1+x)^m=(1+x)^{n+m}$.

Answer 2

A better way , think of a situation where you have $(m+n)$ things and have to select $k$ things , you want the number of ways to do so. There are two ways to think which exactly match with RHS and LHS.

Way 1: Its simply choosing $k$ things of $m+n$ things i.e. the LHS.

Way 2 : Take $j$ things off $m$ things and $k-j$(the rest) from $n$ things sum it up from $j=0$ to $j=k$ i.e. the RHS.