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.

lattice path decomposition

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.


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

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

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.