<s>[INST] Interesting combinatorial identities Let $n$ be a strictly positive integer and let $j=0,\dots,n-1$.
By using Mathematica I managed to guess the following identities:
\begin{eqnarray}
\sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m}{j} &=& \frac{1}{2} \binom{2 n}{2j + 1} \\
\sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+1}{j+1} &=& \frac{1}{2} \binom{2 n+1}{2j + 2} + \binom{n-1}{j} \binom{n+1}{j+1} \frac{n(n-j)}{2 (n+1)(j+1)} \\
\sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+2}{j+2} &=& \frac{1}{2} \binom{2 n+2}{2j + 3} + \binom{n-1}{j} \binom{n+2}{j+2} \frac{n(n-j)}{(n+2)(j+1)} \\
\sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+3}{j+3} &=& \frac{1}{2} \binom{2 n+3}{2j + 4} + \binom{n-1}{j} \binom{n+3}{j+3} \frac{n(n-j)(11+5 j+(7+3 j) n)}{(n+2)(n+3)(4+ 2j)(j+1)} \\
\sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+4}{j+4} &=& \frac{1}{2} \binom{2 n+4}{2j + 5} + \binom{n-1}{j} \binom{n+4}{j+4} \frac{2 n(n-j)(5+2 j+(3+ j) n)}{(n+3)(n+4)(2+ j)(j+1)} \\
\sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+5}{j+5} &=& \frac{1}{2} \binom{2 n+5}{2j + 6} + \binom{n-1}{j} \binom{n+5}{j+5} \cdot \\
&&\frac{n(n-j)((137+93 j+16 j^2)+(264+161j+25 j^2)n/2+(62+35 j+ 5 j^2)n^2/2)}{(n+3)(n+4)(n+5)(j+1)(j+2)(j+3)}
\end{eqnarray}
The temptation is strong to write a general conjecture:
\begin{equation}
\sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+a}{j+a} =  \frac{1}{2} \binom{2 n+a}{2j + 1+a} + \binom{n-1}{j} \binom{n+a}{j+a} \cdot\left(\cdots\right)
\end{equation}
Can anyone advise me how to tackle such a problem?. I think that in this particular case the method of generating functions does not lead to a closed form result.
 [/INST] We provide a closed form expression for our sum.
\begin{eqnarray}
&&\sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+a}{j+a}=\\
&&  
\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\binom{a+2 n}{a+2 j+1}-\binom{a+n}{a+j+1} \binom{a+2 n}{j} \, \cdot _3F_2(-j,a+j+1,a+n+1;a+j+2,a-j+2 n+1;1) =\\
&&
\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\binom{a+2 n}{a+2 j+1}-\binom{a+n}{a+j+1} \binom{-j+2 n-1}{j}  \, \cdot _3F_2(-j,a+j+1,j-n+1;a+j+2,j-2 n+1;1)
\end{eqnarray}
We obtained this result by expanding the first binomial factor on the left hand side into a linear combination of binomial factors that are "adjacent" to the second binomial factor , then absorbing the resulting binomial factors into the second binomial factor and finally doing the sum over $m$ using the telescoping property of the binomial factor. Note that the hypergeometric function on the right hand side is a rational function in $n$.
Note: Interestingly enough Gosper's algorithm fails on this sum. If I have time I will explain why this is the case.
</s>