# When is a sum given in closed form?

Let $a>0$ be a real number. Consider a sum: $$S_n(a) := \sum\limits_{k=0}^{n-1} \binom{k-1/3}{-1/3} \binom{k-1/3+a}{-1/3}$$ Note that if $a = 1/3 + h$ where $h$ is a positive integer the term in the sum can be written as $\frac{(-2/3-h)!}{((-1/3)!)^2} \cdot \binom{k-1/3}{-2/3-h} \cdot (k+1)^{(h)}$ and by further expanding the Pochhammer symbol on the right hand side the term can always be written as a linear combination of binomial factors in $k$. On the other hand we know that $\sum\limits_{k=0}^{n-1} \binom{k+a}{b} = \binom{n+a}{b+1} - \binom{a}{b+1}$. Therefore we conclude that if $a=1/3+h$ the sum in question can be written in closed form. In fact the result reads: $$S_n(a) = \binom{n-\frac{1}{3}}{-\frac{1}{3}} \binom{n-\frac{1}{3}+a} {-\frac{1}{3}} \cdot \frac{\left(n+a\right)}{\binom{h+n}{h}} \cdot \frac{\left(\frac{1}{3} (3 h-2)\right)! }{\frac{1}{3}! (1-3 h) h!} \cdot \, _3F_2\left(\frac{1}{3}-h,-h,n+\frac{2}{3};\frac{2}{3}-h,\frac{4}{3}-h;1\right) +{\mathcal S}_0(h)$$ where $${\mathcal S}_0(h) := \frac{\left(\binom{-\frac{1}{3}}{-\frac{2}{3}}-2 \binom{\frac{2}{3}}{\frac{1}{3}}\right) (-1)^h \left(-h-\frac{2}{3}\right)! h!}{3 \Gamma \left(\frac{2}{3}\right)^2}$$ Now, my question is can we prove that it is only if $a=1/3+h$ that the sum is given in closed form?

We are using Gosper's algorithm to provide the proof. Let $t_k$ denote the term in the sum. Then: $$r_k := \frac{t_{k+1}}{t_k} = \frac{(3 k+2)(3 k+ 3 a+2)}{9(k+1)(k+a+1)} = \frac{(3 k+2)(3 q k + 3 p + 2 q)}{(3 k+3)(3 q k +3 p +3 q)}$$ where $a = p/q$.Now, according to the algorithm we need to write the ratio $r_k$ in the form: $$r_k = \frac{a(k)}{b(k)} \cdot \frac{c(k+1)}{c(k)}$$ where $gcd(a(k),b(k+h) = 1$ for all nonegative integers $h$. We need to ''divide out'' common factors from both the numerator and create the term $c_k$ out of them. There are now two cases. Firstly, the top-right and the bottom-left factors are multiples iff $3 p+ 2 q = (3 + 3 h) q$. In this case $p/q = 1/3 + h$ and: $$r_k = \frac{3k+2}{3 k+ 3 h+4} \cdot \frac{(k+2)^{(h)}}{(k+1)^{(h)}}$$ and therefore $a_k = 3 k+2$, $b_k = 3 k+3 h+4$ and $c_k = (k+1)^{(h)}$. Now, the next step is to seek polynomial solutions to the recurrence $$a_k x_{k+1} - b_{k-1} x_k = c_k$$ and the final solution reads: $$S_n = t_n \cdot \frac{3 n+3 h+1}{(n+1)^{(h)}} \cdot \left( \sum\limits_{p=0}^h {\mathcal A}_p^{(h)} n^p\right) + S_0$$ where \begin{eqnarray} {\mathcal A}_p^{(h)}= \left( \begin{array}{rrrrrr} 1 \\ \frac{1}{2} & 1 \\ \frac{4}{5} & 2 & 1 \\ \frac{21}{10} &\frac{59}{10} & \frac{9}{2} & 1 \\ \frac{84}{11} & \frac{116}{5} & \frac{109}{5} & 8 & 1 \\ \frac{390}{11} & \frac{1256}{11} & \frac{245}{2} & 58 & \frac{25}{2} & 1 \\ \dots \end{array} \right) \end{eqnarray} and $$S_0 = -\frac{\sqrt{3}}{\pi}\left(\frac{3}{2},\frac{9}{4},\frac{27}{10},\frac{243}{80},\cdots\right)$$ Now we consider the second case. Here the top-left and the bottom-right terms are multiples. This happens iff $3 p+3 q =(2+3 h) q$ which gives $p/q = -1/3 + h$ and $h$ is negative. Then we have: $$r_k = \frac{3 k+3 h+1}{3 k+3} \cdot \frac{(k +1 + h + 2/3)^{(|h|)}}{(k + h + 2/3)^{(|h|)}}$$ and therefore $a_k=3 k +3 h+1$, $b_{k} = 3 k+3$ and $c_k = (k+h+2/3)^{(|h|)}$. The final solution reads: $$S_n = t_n \cdot \frac{3 n}{(n+h+2/3)^{(|h|)}} \cdot \left(\sum\limits_{j=0}^{|h|} {\mathcal B}_p^{(h)} n^p\right)$$ where \begin{eqnarray} {\mathcal B}_p^{(h)}= \left( \begin{array}{c} \{1\} \\ \left\{-\frac{5}{6},1\right\} \\ \left\{\frac{71}{45},-\frac{8}{3},1\right\} \\ \left\{-\frac{1243}{270},\frac{277}{30},-\frac{11}{2},1\right\} \\ \left\{\frac{80638}{4455},-\frac{5474}{135},\frac{457}{15},-\frac{28}{3},1\right\} \\ \left\{-\frac{239054}{2673},\frac{193432}{891},-\frac{10217}{54},\frac{682}{9},-\frac{85}{6},1\right\} \\ \end{array} \right) \end{eqnarray}