Proof binomial coefficient by induction i have to show that 
$\sum_{j=0}^n 
\binom{n}{j} * 
\binom{m}{k-j} = 
\binom{n+m}{k}$
is valid.
I tried to do it by induction, the induction beginning fits, but unfortunately, I don't know how to the induction step. I have been failing now for hours, is there someone who can help me, please?
 A: It's coefficient of $x^k$ in $(1+x)^{m+n}$ or see Vandermondes identity as I see you don't need binomial proof .
A: I was able to prove the result without using Mathematical Induction. Here are my workings:
Consider:
$$
\begin{equation*} 
(1+x)^n(1+x)^m = \Bigg(1+\binom{n}{1}x + \binom{n}{2}x^2+...+\binom{n}{n}x^n\Bigg)\Bigg(1+\binom{m}{1}x + \binom{m}{2}x^2+...+\binom{m}{m}x^n\Bigg)
\end{equation*}
\tag{1}
$$
Now, coefficient of $x^k$ from $(1)$ is:
$$
\binom{n}{0}\binom{m}{k} + \binom{n}{1}\binom{m}{k-1}+...\binom{n}{k}\binom{m}{0}
\tag{A}
$$
But,
$$
(1+x)^n(1+x)^m=(1+x)^{m+n}
\tag{2}
$$
Again, coefficient of $x^k$ from $(2)$ is;
$$
\binom{n+m}{k}
\tag{B}
$$ 
Finally, from $(A)$ and $(B)$, we get:
\begin{align*}
&\binom{n}{0}\binom{m}{k} + \binom{n}{1}\binom{m}{k-1}+...\binom{n}{k}\binom{m}{0} = \binom{n+m}{k}\\
&\implies \sum_{j=0}^{n}\binom{n}{j}\binom{m}{k-j} = \binom{m+n}{j}
\end{align*}
A: Using the recurrence relation for Pascal's Triangle, the inductive step can be shown as
$$
\begin{align}
\sum_{j=0}^n\binom{n}{j}\binom{m}{k-j}
&=\sum_{j=0}^n\binom{n}{j}\left[\binom{m-1}{k-j}+\binom{m-1}{k-j-1}\right]\tag{1}\\
&=\sum_{j=0}^n\binom{n}{j}\binom{m-1}{k-j}+\sum_{j=0}^n\binom{n}{j}\binom{m-1}{k-j-1}\tag{2}\\
&=\binom{n+m-1}{k}+\binom{n+m-1}{k-1}\tag{3}\\
&=\binom{n+m}{k}\tag{4}
\end{align}
$$
Explanation:
$(1)$: use Pascal's Triangle recurrence
$(2)$: separate sums
$(3)$: use inductive hypothesis for case $n+m-1$
$(4)$: use Pascal's Triangle recurrence  
