On the sum $\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k}$ 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.
 A: 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}

