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?


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}.$$



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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.