# Finding closed form expression for a multiple sum.

Let $n_1$, $n_2$ and $m$ be non-negative integers and let $\theta_1$ and $\theta_2$ be real numbers subject to $\frac{\theta_1}{\theta_2} = 1+m$. We consider a following multiple sum: \begin{eqnarray} {\mathcal S}_{n_1}^{(n_2)}\left( \theta_1,\theta_2\right) := \sum\limits_{0 \le p \le p_1 \le \cdots \le p_{n_2-1} \le n_1} \prod\limits_{j=1}^{n_2} \binom{p_{j-1} + j \frac{\theta_1}{\theta_2} - 1}{\frac{\theta_1}{\theta_2}-1} \binom{p_{j-1} + j \frac{\theta_1}{\theta_2} +\theta_1 - 1}{\frac{\theta_1}{\theta_2}-1} \end{eqnarray} By using Gosper's algorithm, for example, it is easy to see that the multiple sum is always given as a hypergeometric term. Therefore, with little help of Mathematica, we have found the following closed form solution: \begin{eqnarray} {\mathcal S}_{n_1}^{(n_2)}\left( \theta_1,\theta_2\right) = \left( 1+n_1\right)^{(n_2 (m+1))} \cdot \sum\limits_{l=0}^{n_2 \cdot m} {\mathcal A}_l^{(n_2)} \cdot \left(n_1+n_2(m+1)+1\right)^{(l)} \end{eqnarray} Here the coefficients ${\mathcal A}_l^{(n_2)}$ do not depend on $n_1$ and they satisfy a following recursion relation: \begin{eqnarray} &&{\mathcal A}_L^{(n_2)} = \frac{1}{(L+(m+1) n_2) }\\&& \sum\limits_{l=0}^m \sum\limits_{l_1=0}^{(n_2-1) m} \frac{l_1! (-1)^{l+L+l_1} (-l+m+1)^{(2 l)} 1_{0\le L-l \le (n_2-1) m} 1_{L \le l+l_1} \cdot {\mathcal A}_{l_1}^{(n_2-1)}} {l! (L-l)! (l-L+l_1)! (L-l_1+m)! (-l+m \theta_2+\theta_2)^{(l)}} \end{eqnarray} for $L=0,\cdots,n_2 \cdot m$ and $n_2 \ge 1$ subject to ${\mathcal A}^{(0)}_0 = 1$. Here $x^{(l)} := x \cdot (x+1) \cdot \dots \cdot (x+l-1)$ is the upper Pochhammer symbol. Now the question is is it possible to find a 'closed form solution' for the recursion relation above?

Let us denote $f^{(\delta)}_{n_2} := {\mathcal A}^{(n_2)}_{n_2 \cdot m- \delta}$ for $\delta=0,1,2,\cdots$ subject to $f^{(\delta)}_0 = \delta_{\delta,0}$. Denote also $(\tilde{l},\tilde{l_1}) := (m-l,(n_2-1)\cdot m-l_1)$.
Now take $\delta=0$. Because of the Heaviside function $1_{L \le l+l_1}$ the double sum reduces to one term only, that corresponding to $(\tilde{l},\tilde{l_1})=(0,0)$ the recurrence relation is of degree one and we immediately get: $$f^{(0)}_{n_2} = \frac{\Theta^{n_2}}{n_2!}$$ where $\Theta := \Gamma[m(-1+\theta_2) + \theta_2]/((1+2 m) \cdot m! \cdot \Gamma[(m+1)\theta_2])$.
Now take $\delta=1$. Now there are only three terms in the multiple sum, namely those corresponding to $(\tilde{l},\tilde{l_1})=\left\{ (0,0), (1,0), (0,1) \right\}$. Therefore the recurrence relation has a form: $$f^{(1)}_{n_2} = a_{n_2} f^{(1)}_{n_2-1} + b_{n_2}$$ where \begin{eqnarray} a_{n_2} &=& \frac{(1+2 m) \Theta}{\left[-1+n_2(2m+1)\right]} \\ b_{n_2} &=& \sum\limits_{\xi=1}^2 {\mathbb a}_\xi \frac{\Theta^{n_2}}{\left[-1+n_2(2m+1)\right](n_2-\xi)!} \\ ({\mathbb a}_2,{\mathbb a}_1) &=& \left(-2 m^2 (1+2 m),m(1+2 m) (m(-1+\theta_2)+\theta_2)\right) \end{eqnarray} The solution to our recurrence (subject to initial conditions $f^{(1)}_0=0$) is clearly given as: \begin{eqnarray} f^{(1)}_{n_2} &=& \sum\limits_{j=0}^{n_2-1} \left(\prod\limits_{l=0}^{j-1} a_{n_2-l} \right) \cdot b_{n_2-j} \\ &=& \sum\limits_{\xi=1}^2 \sum\limits_{j=0}^{n_2-1} \left( \prod\limits_{l=0}^{j-1} \frac{(1+ 2 m) \Theta}{[-1+(n_2-l)(2 m+1)]}\right) \cdot \left\{ \frac{{\mathbb a}_\xi}{[-1+(n_2-j)(2 m+1)]} \cdot \frac{\Theta^{n_2-j}}{(n_2-\xi-j)!} \right\} \\ &=& \sum\limits_{\xi=1}^2 \frac{{\mathbb a}_\xi}{[-1+ n_2 (2 m+1)]} \sum\limits_{j=0}^{n_2-1} \frac{(-1)^j}{\left(\frac{1}{2 m+1} - n_2+1\right)^{(j)}} \cdot \frac{(-1)^{j+\xi} (-n_2)^{(\xi+j)}}{1} \cdot \frac{\Theta^{n_2}}{n_2!} \\ &=& \sum\limits_{\xi=1}^2 \frac{{\mathbb a}_\xi}{[-1+ n_2 (2 m+1)]} \cdot F_{2,1} \left[\begin{array}{ll} 1 & -n_2 + \xi \\ \frac{1}{2 m+1} -n_2+1\end{array};1\right] \cdot (-1)^\xi (-n_2)^{(\xi)} \cdot \frac{\Theta^{n_2}}{n_2!} \\ &=& \sum\limits_{\xi=1}^2 \frac{{\mathbb a}_\xi}{[-1+ n_2 (2 m+1)]} \cdot \frac{[-1+n_2(2m+1)]}{[-1+\xi(2 m+1)]} \cdot (-1)^\xi (-n_2)^{(\xi)} \cdot \frac{\Theta^{n_2}}{n_2!} \\ &=& \left( \sum\limits_{\xi=1}^2 \frac{{\mathbb a}_\xi (-1)^\xi (-n_2)^{(\xi)}}{[-1+ \xi (2 m+1)]} \right) \cdot \frac{\Theta^{n_2}}{n_2!} \end{eqnarray} From that above we conjecture that: $$f^{(\delta)}_{n_2} = {\mathcal P}_\delta^{(\dots)} (n_2) \cdot \frac{\Theta^{n_2}}{n_2!}$$ where ${\mathcal P}_\delta^{(\dots)} (n_2)$ is a polynomial in $n_2$.
Now we take $\delta=2$. Clearly now we have $(\tilde{l},\tilde{l}_1) = \left\{(0,0),(1,0),(0,1),(2,0),(1,1),(0,2)\right\}$. The recurrence has a very similar form to that before: $$f^{(2)}_{n_2} = a_{n_2} f^{(2)}_{n_2-1} + b_{n_2}$$ where \begin{eqnarray} a_{n_2} &=& \frac{(1+2 m) \Theta}{\left[-2+n_2(2m+1)\right]} \\ b_{n_2} &=& \sum\limits_{\xi=1}^4 {\mathbb a}^{(2)}_\xi \frac{\Theta^{n_2}}{\left[-2+n_2(2m+1)\right](n_2-\xi)!} \end{eqnarray} where $\left\{{\mathbb a}^{(2)}_\xi\right\}_{\xi=1}^4$ are some rational functions in $m$ too lengthy--unwieldy-- to be written out in here. All we have to do is to repeat the calculations from above with some slight modifications. Since again the initial conditions are $f^{(2)}_0=0$ we have: \begin{eqnarray} f^{(2)}_{n_2} &=& \sum\limits_{j=0}^{n_2-1} \left(\prod\limits_{l=0}^{j-1} a_{n_2-l} \right) \cdot b_{n_2-j} \\ &=& \sum\limits_{\xi=1}^4 \sum\limits_{j=0}^{n_2-1} \left( \prod\limits_{l=0}^{j-1} \frac{(1+ 2 m) \Theta}{[-2+(n_2-l)(2 m+1)]}\right) \cdot \left\{ \frac{{\mathbb a}^{(2)}_\xi}{[-2+(n_2-j)(2 m+1)]} \cdot \frac{\Theta^{n_2-j}}{(n_2-\xi-j)!} \right\} \\ &=& \sum\limits_{\xi=1}^4 \frac{{\mathbb a}^{(2)}_\xi}{[-2+ n_2 (2 m+1)]} \sum\limits_{j=0}^{n_2-1} \frac{(-1)^j}{\left(\frac{2}{2 m+1} - n_2+1\right)^{(j)}} \cdot \frac{(-1)^{j+\xi} (-n_2)^{(\xi+j)}}{1} \cdot \frac{\Theta^{n_2}}{n_2!} \\ &=& \sum\limits_{\xi=1}^4 \frac{{\mathbb a}^{(2)}_\xi}{[-2+ n_2 (2 m+1)]} \cdot F_{2,1} \left[\begin{array}{ll} 1 & -n_2 + \xi \\ \frac{2}{2 m+1} -n_2+1\end{array};1\right] \cdot (-1)^\xi (-n_2)^{(\xi)} \cdot \frac{\Theta^{n_2}}{n_2!} \\ &=& \sum\limits_{\xi=1}^4 \frac{{\mathbb a}^{(2)}_\xi}{[-2+ n_2 (2 m+1)]} \cdot \frac{[-2+n_2(2m+1)]}{[-2+\xi(2 m+1)]} \cdot (-1)^\xi (-n_2)^{(\xi)} \cdot \frac{\Theta^{n_2}}{n_2!} \\ &=& \left( \sum\limits_{\xi=1}^4 \frac{{\mathbb a}^{(2)}_\xi (-1)^\xi (-n_2)^{(\xi)}}{[-2+ \xi (2 m+1)]} \right) \cdot \frac{\Theta^{n_2}}{n_2!} \end{eqnarray} At this point we conjecture that the coefficients have the following form: $$f^{(\delta)}_{n_2} = {\mathcal A}^{(n_2)}_{n_2 \cdot m- \delta} = \left(\sum\limits_{\xi=1}^{2 \delta} \frac{ {\mathbb a}^{(\delta)}_\xi \cdot (-1)^\xi \cdot (-n_2)^{(\xi)} }{ [-\delta + \xi (2m+1)] } \right) \cdot \frac{\Theta^{n_2}}{n_2!}$$ where $\left\{{\mathbb a}^{(\delta)}_\xi \right\}_{\xi=1}^{2 \delta}$ do not depend on $n_2$.