What is the value of $ \sum\limits_{k=0}^{n-1}\binom {n-k-1}{j-1} \binom {r+k}{j+k}$?

Question

What is the value of $$ \sum_{k=0}^{n-1}\binom {n-k-1}{j-1} \binom {r+k}{j+k}$$ where $r \ge j \ge 1$?

I know that

$$ \sum_{k=0}^{n}\binom {n-k}{m}\binom{r+k}{s} = \binom {n+r+1}{m+s+1} \text{ where }n,m \ge0,\text{ and }s\ge r\ge 0$$

Please notice that second term of the first summation can be replaced by

$$ \binom {r+k}{r-j} $$

Then the first summation becomes

$$ \sum_{k=0}^{n-1}\binom {n-k-1}{j-1} \binom {r+k}{r-j} $$ which is identical to the second summation but doesn't satisfy the condition in second summation that is $ r \ngeq r - j$ since both $ r,j \ge 1 $

Is it possible to reduce the first summation similar to the second summation?

Answer 1

Here is some additional information which shows the two binomial expressions have different type. We transform both identities so that the different type becomes somewhat more evident. We start with a look at the second binomial identity.

Second binomial identity:

\begin{align*} \sum_{k=0}^n\binom{n-k}{m}\binom{r+k}{s}=\binom{n+r+1}{m+s+1}\qquad\qquad n,m\geq 0, s\geq r\geq 0 \end{align*} Since $\binom{n-k}{m}=0$ if $n-k<m$ the upper limit of the sum is effectively $n-m$ and we get \begin{align*} \sum_{k=0}^{n-m}\binom{n-k}{m}\binom{r+k}{s}=\binom{n+r+1}{m+s+1}\qquad\qquad n,m\geq 0, s\geq r\geq 0 \end{align*} We introduce a new parameter $t$ with $s=r+t$ and the condition $s\geq r\geq 0$ is transformed to $r,t\geq 0$.

We finally obtain \begin{align*} \sum_{k=t}^{n-m}\binom{n-k}{m}\binom{r+k}{r\color{blue}{+t}}=\binom{n+r+1}{m+r+t+1}\qquad\qquad n,m,r,t\geq 0\tag{1} \end{align*} Note, the lower limit of the sum starts with $k=t$, since otherwise $r+k<r+t$ and $\binom{r+k}{r+t}=0$.

First binomial expression:

In order to obtain a representation which is as close as possible to (1) we replace in the first binomial expression $n-1$ with $n$ and we replace $j-1$ with $m$. We obtain

\begin{align*} \sum_{k=0}^{n}\binom {n-k}{j-1} \binom {r+k}{r-j} &=\sum_{k=0}^{n}\binom {n-k}{m} \binom {r+k}{r-(m+1)}\\ \end{align*}

Here we can tighten the upper limit as we did in (1) but we can't tighten the lower limit, since $r+k\geq r-(m+1)$ for $k\geq 0$.

We obtain

\begin{align*} \sum_{k=0}^{n-m}\binom {n-k}{m} \binom {r+k}{r\color{blue}{-(m+1)}}\qquad\qquad n,m,r\geq 0\tag{2} \end{align*}

Conclusion:

• While the range of $n,m$ and $r$ is equal in both expressions (1) and (2) the range of $t\geq 0$ in (1) corresponds to the range $-(m+1)<0$.

• The non-negativity of $t$ and the negativity of $-(m+1)$ is a conflict, which can't be corrected. So, the binomial expressions are of different type.

• The binomial expression in (1) has $n-m-t+1$ summands, while the expression in (2) has $n-m+1$ summands.

Answer 2

$$ \begin{align} \sum_{k=0}^{n-1}\binom{n-k-1}{j-1}\binom{r+k}{j+k} &=\sum_{k=0}^{n-1}\binom{n-k-1}{j-1}\binom{r+k}{r-j} \end{align} $$ which looks like $\binom{n+r}{r}$, but we are missing some $-j\le k\lt0$.

---

For example, let $n=6$, $j=3$, and $r=4$ $$ \begin{align} \sum_{k=0}^{n-j}\binom{n-k-1}{j-1}\binom{r+k}{r-j} &=\overbrace{\binom{5}{2}\binom{4}{1}}^{k=0}+\overbrace{\binom{4}{2}\binom{5}{1}}^{k=1}+\overbrace{\binom{3}{2}\binom{6}{1}}^{k=2}+\overbrace{\binom{2}{2}\binom{7}{1}}^{k=3}\\ &=95 \end{align} $$ But $\binom{10}{4}=210$. Where is the missing $115$? $$ \begin{align} \sum_{k=-j}^{-1}\binom{n-k-1}{j-1}\binom{r+k}{r-j} &=\overbrace{\binom{8}{2}\binom{1}{1}}^{k=-3}+\overbrace{\binom{7}{2}\binom{2}{1}}^{k=-2}+\overbrace{\binom{6}{2}\binom{3}{1}}^{k=-1}\\ &=115 \end{align} $$