Induction with binomial coefficient

Question

Is mathematical Induction possible with this sigma sign?

$A(k) =\sum_{j=0}^{k} \binom{m}{j}\binom{n}{k-j} = \binom{m+n}{k}$

$A(k+1) = \sum_{j=0}^{k+1} \binom{m}{j}\binom{n}{(k+1)-j} = \binom{m+n}{(k+1)}$

I started with

$A(k+1) = \sum_{j=0}^{k+1} \binom{m}{j}\binom{n}{(k+1)-j} $

$ = \sum_{j=0}^{k} \binom{m}{j}\binom{n}{(k+1)-j} + \binom{m}{k+1}*\binom{n}{0}$

$ = \sum_{j=0}^{k} \binom{m}{j}\binom{n}{(k+1)-j} + \binom{m}{k+1}$

I know i should use my $A(k)$ but I dont know how to...

Is there a way i can change the $\binom{n}{k+1-j}$ to $\binom{n}{k-j}$ in the second binominal coefficient of the sum?

Answer 1

You can use Pascal formula $$\binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}.$$

But actually a combinatory proof is much better.

Suppose there is $n$ mens an $m$ women. To make $k$ groupe with $m+n$ people you obviously have $\binom{n+m}{k}$ possibility. But to count the number of those group you can do as follow: you have either $\binom{n}{0}$ men and $\binom{m}{k}$ women, or $\binom{n}{1}$ man and $\binom{m}{k-1}$ women, or $\binom{n}{2}$ men and $\binom{m}{k-2}$ women...

at the end you get $$\sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}.$$

Answer 2

Hint:

You don't need induction. $\binom mj$ is the coefficient of $x^j$ when you expand $(1+x)^j$ with the binomial formula. So all you have to do is computing the coefficient of $x^k$ when you expand $(1+x)^m(1+x)^n$ in two different ways.