Closed form solution of a hypergeometric sum. The binomial theorem is one of the best known hyper-geometric sums for whom a closed form expression exists. The natural question is whether generalizations exist . In particular I would like to know if the following sum :
\begin{equation}
S^{(k)}_{p,q}(x) := \sum\limits_{l=0}^{k-2} \binom{k+p+l}{2 l+q} (-x)^l
\end{equation}
for $p,q \in {\mathbb N}$  is given in closed form? I have found a positive answer. Firstly I used sister Celine's algorithm to find the recursion relation for the term in the sum. From that by summing over the paramater $l$ I found the recursion relation for the sum itself. It reads:
\begin{eqnarray}
S^{(k)}_{p,q} + (x-2) S^{(k+1)}_{p,q} + S^{(k+2)}_{p,q}  &=& \binom{k+p}{q-2}  +\\
&&(-x)^{k-1} (x \binom{2 k+p}{p-q}-2 x \binom{2 k+p+1}{p-q+1}-\binom{2 k+p-1}{p-q+1})
\end{eqnarray}
now since the recursion relation has constant coefficients a closed form expression can always be found by solving the characteristic equation and then convolving the respective power functions with the right hand side. The solution reads:
\begin{eqnarray}
&&S^{(k)}_{p,q} =\\
&& 
\left(\frac{\sin(\phi(k-1))}{\sin(\phi)} f_{p,q-2}^{(\phi)} - \frac{\sin(\phi(k-0))}{\sin(\phi)}  f_{p+1,q-2}^{(\phi)} + f_{p+k,q-1}^{(\phi)}\right) 1_{q\ge 2} +\\
&&-
\left(\frac{\sin(\phi(k-1))}{\sin(\phi)} \tilde{f}_{p,p-q}^{(\phi)} + x \frac{\sin(\phi(k-0))}{\sin(\phi)} f_{p+2,p-q}^{(\phi)} + (-x)^k f_{p+2 k,p-q}^{(\phi)}\right) 1_{p-q\ge 0} +\\
&&2\left(\frac{\sin(\phi(k-1))}{\sin(\phi)} \tilde{f}_{p+1,p-q+1}^{(\phi)} + x \frac{\sin(\phi(k-0))}{\sin(\phi)}  f_{p+3,p-q+1}^{(\phi)} + (-x)^k f_{p+1+2 k,p-q+1}^{(\phi)}\right) 1_{p-q+1\ge 0} +\\
&&-\left(\frac{\sin(\phi(k-2))}{\sin(\phi)} \tilde{f}_{p+1,p-q+1}^{(\phi)} + x \frac{\sin(\phi(k-1))}{\sin(\phi)} f_{p+3,p-q+1}^{(\phi)} + (-x)^{k-1} f_{p-1+2 k,p-q+1}^{(\phi)}\right) 1_{p-q+1\ge 0}\\
\end{eqnarray}
where  $k \ge 2$.
Here $\phi := \arccos(1-x/2)$ and:
\begin{eqnarray}
f_{p,q}^{(\phi)} &:=& \left. \frac{1}{q!} \frac{d^q}{d \xi^q} \left(\frac{\xi^p}{1-2 \xi \cos(\phi)+\xi^2}\right)\right|_{\xi=1}\\
\tilde{f}_{p,q}^{(\phi)} &:=& \left. \frac{1}{q!} \frac{d^q}{d \xi^q} \left(\frac{\xi^p}{1+2 x \xi^2 \cos(\phi)+x^2 \xi^4}\right)\right|_{\xi=1}
\end{eqnarray}
Now, I reiterate the question. Is it possible to do the sum when the number 2 in the binomial factor in the sum in question is replaced by some integer greater or equal three?
 A: Let us answer the second question first. In other words we define:
\begin{equation}
S^{(k)}_{n,p,q}(x) := \sum\limits_{l=0}^{k-2} \binom{k+p+l}{n \cdot l+q} (-x)^l
\end{equation}
for $q \ge 1+n+p$ and $k \ge q-n-p,\dots,\infty$ and $n=1,2,\dots$. Again, using sister Celine's algorithm we easy establish that a the sum in question satisfies a following recursion relation:
\begin{equation}
\sum\limits_{i=0}^n S^{(k+i)}_{n,p,q} \cdot \binom{n}{i} (-1)^i + (-1)^n x S^{(k+1)}_{n,p,q} = (-1)^n \binom{k+p}{q-n} 1_{k \ge q-n-p}
\end{equation}
Now, again since this recursion relation has coefficients that do not depend on $k$ it can always be solved in terms of roots of the characteristic equation and convolutions of powers of those roots with the right hand side. A standard method for solving  such equations is the method of Greens functions. In other words we assume that:
\begin{equation}
S^{(k)}_{n,p,q} = \sum\limits_{l=0}^\infty G_{k,l} \cdot rhs_l
\end{equation}
where $rhs_l$ is the right hand side of the recursion relation and the Greens function itself satisfies the recursion relation with its right hand side being replaced by $\delta_{k,l}$. Here the Green's function is given as:
\begin{equation}
G_{k,l} = \left\{
\begin{array}{rr} \sum\limits_{i=1}^n C_i^{+} \cdot \lambda_i^k & \mbox{for $l\ge k$}\\ \sum\limits_{i=1}^n C_i^{-} \lambda_i^k & \mbox{for $0 \le l \le k-1$}\end{array}
\right.
\end{equation}
where $\left\{ \lambda_i \right\}_{i=1}^n$ are roots of the characteristic equation $(1-\lambda)^n + (-1)^n x \lambda = 0$.
Inserting the above into the recursion relation for the Greens function and evaluating the later equation at $k=l-j$ for $j=0,\dots,n-1$ and then solving for the constants $C^{-}$ we get:
\begin{equation}
C_i^{-}= C_i^{+} + \frac{\lambda_i^{-1-l}}{\prod\limits_{j\neq i}(\lambda_i - \lambda_j)}
\end{equation}
for $i=1,\dots,n$. Therefore the sum in question reads:
\begin{equation}
S^{(k)}_{n,p,q} = \left(\sum\limits_{i=1}^n C_i^{+} \cdot \lambda_i^k\right) \quad + \quad \sum\limits_{l=0}^{k-1} \sum\limits_{i=1}^n \frac{\lambda_i^{-1-l+k}}{\prod\limits_{j\neq i}(\lambda_i - \lambda_j)} \cdot (-1)^n \cdot \binom{l+p}{q-n} 1_{l \ge q-n-p}
\end{equation}
where the constants $C^{+}_i$ for $i=1,\dots,n$ are determined from initial conditions, ie from the values of our sum at $k=1,2,\dots,n$. Finally note that the sum over the index $l$ in the equation above can be done using the standard trick, ie expressing the binomial factor as a higher order derivative with respect to some dummy variable, summing up the resulting geometric series and taking the dummy variable equal to unity at the end of the calculation.
