On the sum $\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k}$

Question

Let $n$ be a non-negative integer. Does there always exist a polynomial $P_n(a,b)$ such that for all integers $a > b \geq n/2$ we have $$ \sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k} = \binom{2a-1}{a+b} P_n(a,b)\quad ? $$ For small values of $n$ this is easily verified using Gosper's algorithm, for example $$P_0(a,b) = a+b,\qquad P_1(a,b) = \tfrac{2}{3}(a+b)(b^2 +a -1), $$ but I am struggling to prove the general case. Any suggestions or literature references on this problem?

---

Here are some details on Gosper's algorithm. Let us denote the summand by $t(k) = \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k}$ and let $$p(k) = (k-\tfrac12n+1)_n(k-\tfrac12n+\tfrac12)_{n+1}, \quad q(k) = a-k-1, \quad r(k)=a+k$$ where $(x)_n = x(x+1)\cdots(x+n-1)$. Then we have $$ \frac{t(k+1)}{t(k)} = \frac{q(k)}{r(k+1)}\frac{p(k+1)}{p(k)}.$$ According to Gosper, $T(k+1)-T(k)=t(k)$ has a hypergeometric term solution $T(k)$ iff there exists a polynomial $s(k)$ of degree $2n$ (with coefficients that depend on $a$) that solves \begin{equation} \tag{1} p(k) = q(k) s(k+1) - r(k)s(k). \end{equation} If such a solution exists, then $$T(k) = \frac{r(k)}{p(k)} t(k)s(k)\quad \text{and}\quad P_n(a,b) = \frac{T(a)-T(b)}{\binom{2a-1}{a+b}} = -\frac{2^{2n+1}}{(2n+1)!}(a+b)\,s(b)$$ fulfilling my request. The linear mapping $s(k) \mapsto q(k) s(k+1) - r(k)s(k)$ from polynomials of degree $2n$ to those of rank $2n+1$ is easily seen to be injective, but it seems difficult to show that $p(k)$ lies in its image for general $n$.

Update: I have included a proof in an answer below, but I'd still be interested in literature references.

Answer 1

Actually, checking whether $p(k)$ lies in the image of $s(k) \mapsto q(k) s(k+1) - r(k)s(k)$ turns out to be not too difficult after all. We need to determine a single linear condition that spans the cokernel of the linear mapping. A convenient way to do this is by turning $q(k) s(k+1) - r(k)s(k)$ into a differential operator and seeking a (formal) power series $V(x)$ solving \begin{align} 0 &= \left[s(1+\partial_x)q(\partial_x) - s(\partial_x)r(\partial_x) \right] V(x)\big|_{x=0} \\ &=\left[e^{-x}s(\partial_x)e^{x}q(\partial_x) - s(\partial_x)r(\partial_x) \right] V(x)\big|_{x=0} \\ &=s(\partial_x)\left[e^{x}q(\partial_x) - r(\partial_x) \right] V(x)\big|_{x=0}. \end{align} Hence, a solution to \begin{equation} 0 = \left[e^{x}q(\partial_x) - r(\partial_x) \right] V(x) = (e^x(a-1)-a)V(x)-(e^x+1)V'(x) \end{equation} will do for any $n\geq 0$ and any polynomial $s(k)$. One easily finds \begin{equation} V(x) = e^{-ax} (1+e^{x})^{2a-1} = e^{-x/2} (2\cosh(x/2))^{2a-1}. \end{equation} It remains to show that $p(\partial_x) V(x)|_{x=0}=0$. This follows from \begin{equation} p(\partial_x) V(x)\big|_{x=0} = p(\partial_x-\tfrac{1}{2}) e^{x/2}V(x)\big|_{x=0} = p(\partial_x-\tfrac{1}{2}) (2\cosh(x/2))^{2a-1}\big|_{x=0}, \end{equation} which vanishes because $p(\partial_x-1/2)$ is odd in $\partial_x$, while $(2\cosh(x/2))^{2a-1}$ is an even power series in $x$.

This shows that the recursion equation (1) has a unique polynomial solution $s(k)$. Moreover the coefficients of $s(k)$ are seen to be polynomials in $a$, since the linear mapping $s(k) \mapsto q(k) s(k+1) - r(k)s(k)$ is essentially upper-triangular (in the monomial basis) with a diagonal that is independent of $a$. QED.

In fact this demonstrates an equivalence:

Let $p(k)$ be a polynomial. Then $\sum_{k=b}^{a-1} p(k)\binom{2a-1}{a+k}$ is given by a hypergeometric term in $b$ if and only if $p(k-1/2)$ is odd in $k$. In that case there exists a polynomial $P(a,b)$ such that \begin{equation}\sum_{k=b}^{a-1} p(k)\binom{2a-1}{a+k} = \binom{2a-1}{a+b} P(a,b).\qquad (a>b) \end{equation}