Prove $\sum\limits_{l=0}^m\binom{k+l}{k}\binom{n-k-1+m-l}{n-k-1}=\binom{n+m}{m}$ 
Prove that $$\sum_{l=0}^m\binom{k+l}{k}\binom{n-k-1+m-l}{n-k-1}=\binom{n+m}{m}$$

My solution: I tried to use Vandermonde's identity:
\begin{align}
\sum_{l=0}^m\binom{k+l}{k}\binom{n-k-1+m-l}{n-k-1}&=\sum_{l=0}^m\binom{k+l}{l}\binom{n-k-1+m-l}{m-l}\\
&=\binom{n+m-1}{m}
\end{align}
Where am I wrong? How to prove it correct way? 
 A: Vandermonde's identity says
$$ \sum_{\color{blue}k = 0}^r \binom{m}{\color{blue}k}\binom{n}{r-\color{blue}k} = \binom{m + n}{r}. $$
Note where the $k$ appears in the summation (in the bottom only). In your summation, does the index of summation, $l$, appear in the bottom only?
You can prove this identity by considering lattice paths. Let $\mathscr{L}(a,b)$ be the set of North/East lattice paths from $(0,0)$ to $(a,b)$. Then
$$ \mathscr{L}(n,m) \leftrightarrow \biguplus_{l = 0}^m \mathscr{L}(k,l) \times \mathscr{L}(n - (k + 1), m - l). \tag{1} $$
The decomposition is pictured below.

Since $|\mathscr{L}(a,b)| = \binom{a + b}{a} = \binom{a + b}{b}$, the decomposition $(1)$ gives
$$ \binom{m + n}{m} = \sum_{l = 0}^m \binom{k + l}{k} \binom{n - k - 1 + m - l}{n - k - 1}. $$
A: The problem is that for using Vandermonde, you need to have fix numbers in the up part of binomials. You have, instead $$\binom{k+\color{red}{l}}{l}\binom{n-k-1+m-\color{red}{l}}{m-l}.$$
I will go with a combinatorial argument:
Recall that $$\binom{n+m}{n}=|A|=|\{x\in \{0,1\}^{n+m}:|x|_1=n\}|,$$
where $|x|_1=$# of 1's in the string.
Consider, now, the sets $$A_l = \{x\in A:\sum _{i=1}^{k+l} x_i =k \wedge x_{k+l+1}=1  \}.$$
then $A=\bigcup _{l=0}^n A_l$ and $A_l\bigcap A_j=\emptyset$ if $l\neq j.$ So $$\binom{n+m}{n}=|A|=|\bigcup _{l=0}^n A_l|=\sum _{l = 0}^n|A_l|,$$
but for $A_l$ you have to choose the $k$ ones on $k+l$ and $n-k-1$ ones in $n+m-(l+k+)$ so $$|A_l|=\binom{l+k}{k}\binom{n+m-(l+k+1)}{n-k-1}.$$  So your identity follows. 
A: We can use a generalisation of the Vandermonde Identity.

We obtain
  \begin{align*}
\color{blue}{\sum_{l=0}^m}&\color{blue}{\binom{k+l}{k}\binom{n-k-1+m-l}{n-k-1}}\\
&=\sum_{l=0}^m\binom{k+l}{l}\binom{n-k-1+m-l}{m-l}\tag{1}\\
&=(-1)^m\sum_{l=0}^m\binom{-k-1}{l}\binom{-n+k}{m-l}\tag{2}\\
&=(-1)^m\binom{-n-1}{m}\tag{3}\\
&\color{blue}{=\binom{n+m}{m}}\tag{4}\\
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we apply the binomial identity $\binom{p}{q}=\binom{p}{p-q}$ twice.

*In (2) we apply the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ twice.

*In (3) we apply the Chu-Vandermonde Identity.

*In (4) we again apply the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.
