3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ So alternatively, you are summing over all increasing sequences in $\{1,\ldots,N-1\}$ of length $k$? $\endgroup$ – Servaes Apr 2 at 10:35
  • 1
    $\begingroup$ Sorry. Right, that's what I do. $\endgroup$ – Kolya Ivankov Apr 2 at 10:36
  • 1
    $\begingroup$ 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...) $\endgroup$ – Servaes Apr 2 at 10:58
  • 1
    $\begingroup$ (...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$? $\endgroup$ – Servaes Apr 2 at 10:59
3
$\begingroup$

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).$$

$\endgroup$
0
$\begingroup$

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.

I am obliged to G Cab and Servaes for helping me out with this problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.