# A sum of polyharmonic series

Could anyone suggest how to obtain good estimates from above $$\vee$$ below for the following finite series: $$F(N,k):=\sum_{n_1 + \dots + n_k < N, \; n_i\ge 1}\frac{1}{n_1(n_1+n_2)\dots(n_1 + \dots + n_k)}?$$ For $$k=1$$ this is just a harmonic series. One may sort of approximate it by an integral $$\int_{1}^{N-k}x_1^{-1}\int_{x_1+1}^{N-k+1}x_2^{-1}\dots \int_{x_{k-1}+1}^{N-1}x_k\, dx_k\dots dx_1,$$ but this yields neither an upper nor a lower bound that easily.

Alternatively, I am looking for estimates for expanded expressions $$\Phi(N,k) = \sum_{j=0}^{k-1}F(N,j)$$ with $$F(N,0)=1$$, or even $$\Theta(N,k) = \sum_{i=0}^{L}\frac{\Phi(ik,k)}{ik}$$, as some neat cancellations perhaps happen there.

• So alternatively, you are summing over all increasing sequences in $\{1,\ldots,N-1\}$ of length $k$? – Servaes Apr 2 at 10:35
• Sorry. Right, that's what I do. – Kolya Ivankov Apr 2 at 10:36
• If $N\leq k$ then $F(N,k)=0$. Splitting $F(N,k)$ into sums with $n_k=j$ constant yields $$F(N,k)=\sum_{j=k}^{N-1}F(j,k-1).$$ Repeating this twice more yields \begin{eqnarray*} F(N,k) &=&\sum_{j=k}^{N-1}\sum_{i=k-1}^{j-1}F(i,k-2)=\sum_{i=k-1}^{N-2}(N-1-i)F(i,k-2)\\ &=&\sum_{i=k-1}^{N-2}(N-1-i)\sum_{l=k-2}^{i-1}F(l,k-3)=\sum_{l=k-2}^{N-3}C(N,l)F(l,k-3), \end{eqnarray*} where the coefficients $C(N,l)$ are given by \begin{eqnarray*} C(N,l)&=&\sum_{i=l+1}^{N-2}(N-1-i)\\&=&(N-l-2)(N-1)-\frac{(N-2)(N-1)-l(l+1)}{2}\\&=&\tfrac12(N-l-\tfrac54)(N+l+\tfrac74). \end{eqnarray*} (Continued...) – Servaes Apr 2 at 10:58
• (...Continued) Perhaps someone more familiar with such recursions sees a nicer closed form for the coefficients as we repeat this substitution, up to $k$ times? At least it seems that $F(N,k)$ is polynomial of degree $k$ in $N$? – Servaes Apr 2 at 10:59

Not a complete answer, some relatively simple bounds on $$F(N,k)$$. The sum $$F(N,k)$$ runs over all increasing sequences of length $$k$$ in $$\{1,\ldots,N-1\}$$. There are precisely $$\binom{N-1}{k}$$ such sequences, and clearly each summand is at most $$\tfrac{1}{k!}$$, which shows that $$F(N,k)\leq\frac{1}{k!}\binom{N-1}{k}.$$ Similarly, a lower bound $$F(N,k)$$ comes from the fact that every summand is bounded below by $$\frac{1}{N(N-1)(N-2)\cdots(N-k+1)}=\frac{(N-k)!}{N!},$$ which shows that $$F(N,k)\geq\frac{(N-k)!}{N!}\binom{N-1}{k}=\frac{N-k}{N(k!)}=\frac{1}{k!}-\frac{1}{(k-1)!N}$$
Alternatively, here's a proof by induction on $$k$$ that $$F(N,k)\leq(N-k)^k$$ for all $$N,k\geq1$$: For $$k=1$$ and all $$N\geq1$$ we have $$F(N,1)=H_{N-1}\leq(N-1)^1= P(N,1).$$ If $$F(j,k-1)\leq P(j,k-1)$$ for all $$j\in\Bbb{N}$$ then $$F(N,k)=\sum_{j=k}^{N-1}F(j,k-1)\leq\sum_{j=k}^{N-1}P(j,k-1) =\sum_{j=k}^{N-1}(j-(k-1))^{k-1}\leq(N-k)(N-k)^{k-1}=P(N,k).$$
Occasionally, by revisiting the answers to my earlier question, in which the same problem was addressed yet a computational error was made in problem posing, I found out that one can write $$F(N,k)$$ as $$\frac{1}{(N-1)!}\sum_{1\le m_1 < \dots < m_{N-1-k} < N} m_1m_2\dots m_{N-k-1}$$ The sum here is the unsigned Stirling number of the first kind, so that all the established recurrences and estimates may apply.