# 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?

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

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.

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

• Thank you so much, Markus. It's what I needed. – Yuliya Sep 13 '17 at 11:31
• @Yuliya: You're welcome! :-) – Markus Scheuer Sep 13 '17 at 11:32