QUESTION: \begin{equation*} \dbinom{n+m+1}{n}=\sum_{k=0}^n \dbinom{r+k}{k} \dbinom{m+n-r-k}{n-k} \end{equation*} where $n, m, r \geq 0$

I tried proving using binomial coefficient formula $\big[\dbinom{n}{k}=\frac{n!}{k!(n-k)!}\big]$, but dont think its possible with summation, however if it is would it work? Maybe lattice paths would work better, but my understanding of lattice squares is minimal.

So i attempted the proof using binomial theorems and exponent combination laws and i get stuck

\begin{equation*} \sum_{k=0}^n \dbinom{r+k}{k} \dbinom{m+n-r-k}{n-k}=\dbinom{n+m+1}{n} \end{equation*} working with the right side . \begin{equation*}\dbinom{n+m+1}{n}= \sum_n\dbinom{n+m+1}{n}x^n=(1+x)^{n+m+1}\end{equation*} \begin{equation*}=(1+x)^n(1+x)^m(1+x)\end{equation*} or would the next step be \begin{equation*}(1+x)^n(1+x)^{m+1}\end{equation*}

  • 1
    $\begingroup$ I think the LHS should be $\dbinom{n+m}n$, in which case this is just a simple variation of Vandermonde's identity. $\endgroup$ – Prasun Biswas Nov 3 '17 at 2:00
  • 1
    $\begingroup$ @PrasunBiswas no, the LHS is correct: this a "double convolution" (upper and lower terms), in which case the upper term gets a +1. $\endgroup$ – G Cab Nov 3 '17 at 9:24
  • $\begingroup$ @MahlissaJayde: The right-hand side $(1+x)^{n+m+1}$ of your calculation is not valid, since $n$ is the index of the sum and so $n$ can't occur on the right-hand side. $\endgroup$ – Markus Scheuer Nov 3 '17 at 22:32
  • 1
    $\begingroup$ i just realized that. so this approach will not work then. $\endgroup$ – Mahlissa LECKY Nov 3 '17 at 22:39

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{\binom{r+k}{k}\binom{m+n-r-k}{n-k}}\\ &=\sum_{k=0}^n\binom{-r-1}{k}(-1)^k\binom{-m+r-1}{n-k}(-1)^{n-k}\tag{1}\\ &=(-1)^n\binom{-m-2}{n}\tag{2}\\ &\color{blue}{=\binom{n+m+1}{n}}\tag{3} \end{align*}


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

    This way we get for example $\binom{r+k}{k}=\binom{-(-r-k)}{k}=\binom{(-r-k)+k-1}{k}(-1)^k=\binom{-r-1}{k}(-1)^k$ with $-r-k=p$ and $k=q$.

  • In (2) we apply the Chu-Vandermonde identity.

  • In (3) we apply again the binomial identity as in (1).

  • $\begingroup$ perfect (as always!) $\endgroup$ – G Cab Nov 3 '17 at 9:27
  • $\begingroup$ @GCab: You're too friendly, thanks. But sometimes there are nice miniatures, which I don't see straightaway. This post is a nice example where SangchulLee provided a very nice answer to my hint. :-) $\endgroup$ – Markus Scheuer Nov 3 '17 at 9:32
  • 1
    $\begingroup$ @MahlissaJayde: There's always more than one way to do it. Not so clear what you want to know. Some more information to Chu Vandermonde or alternative proofs of your problem? $\endgroup$ – Markus Scheuer Nov 3 '17 at 22:14
  • 1
    $\begingroup$ @MahlissaJayde: I've extended my comment somewhat which might be useful. $\endgroup$ – Markus Scheuer Nov 3 '17 at 22:38
  • 1
    $\begingroup$ i understood that step, thank you its just the elimination of k in step 2 $\endgroup$ – Mahlissa LECKY Nov 3 '17 at 22:41

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.