# Binomial coefficient equality

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*}

• I think the LHS should be $\dbinom{n+m}n$, in which case this is just a simple variation of Vandermonde's identity. – Prasun Biswas Nov 3 '17 at 2:00
• @PrasunBiswas no, the LHS is correct: this a "double convolution" (upper and lower terms), in which case the upper term gets a +1. – G Cab Nov 3 '17 at 9:24
• @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. – Markus Scheuer Nov 3 '17 at 22:32
• i just realized that. so this approach will not work then. – 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*}

Comment:

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

• perfect (as always!) – G Cab Nov 3 '17 at 9:27
• @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. :-) – Markus Scheuer Nov 3 '17 at 9:32
• @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? – Markus Scheuer Nov 3 '17 at 22:14
• @MahlissaJayde: I've extended my comment somewhat which might be useful. – Markus Scheuer Nov 3 '17 at 22:38
• i understood that step, thank you its just the elimination of k in step 2 – Mahlissa LECKY Nov 3 '17 at 22:41