# Estimate for multiple harmonic sum

I am interested in estimating the following family of sums:

$$S_k(n) \equiv \sum_{\substack{n_1, \ldots, n_k \geq 1\\n_1 + \ldots + n_k = n}}\frac{1}{n_1\ldots n_k}$$

where $$k \geq 1, n \geq 1$$. A very simple calculation shows that

$$S_k(n) = \frac{k}{n}\sum_{k - 1 \leq j \leq n - 1}S_{k - 1}(j)$$

and

$$S_k(n) = \frac{k!}{n}\sum_{1 \leq j_1 < j_2 < \ldots < j_{k - 1} \leq n - 1}\frac{1}{j_{k - 1}\ldots j_1}$$

Now, from the recursion formula, one can easily see from interated sum-integral comparison that for $$k$$ fixed, $$n \to \infty$$, $$S_k(n) \sim k\frac{\log(n)^{k - 1}}{n}$$.

However, from numerical experiments, this estimate approximates the result pretty badly for small $$n$$ (actually, typically $$n < e^k$$ I believe) and the behaviour in this region gets worse and worse as $$k$$ increases!

Do you know of any finer technique that would allow me to give a sharper estimate for all finite (i.e not asymptotic) $$k, n$$?

$$\begin{array}{l} \left[ \begin{array}{c} n \\ m \\ \end{array} \right]\quad \left| {\;1 \le n,m} \right.\quad = \\ = \frac{{n!}}{{m!}}\sum\limits_{\begin{array}{*{20}c} {1\, \le \,k_{\,j} } \\ {\,k_{\,1} \, + \,k_{\,2} \, + \, \cdots \, + \,k_{\,m} \, = \,n} \\ \end{array}} {\frac{1}{{k_{\,1} k_{\,2} \cdots k_{\,m} }}} = \\ = \frac{{n!}}{{m!}}\sum\limits_{\begin{array}{*{20}c} {0\, \le \,k_{\,j} } \\ {\,k_{\,1} \, + \,k_{\,2} \, + \, \cdots \, + \,k_{\,m} \, = \,n - m} \\ \end{array}} {\frac{1}{{\left( {k_{\,1} + 1} \right)\left( {k_{\,2} + 1} \right) \cdots \left( {k_{\,m} + 1} \right)}}} = \\ = \sum\limits_{1\, \le \,k_{\,1} \, \le \,k_{\,2} \, \le \, \cdots \, \le \,k_{\,n - m - 1} \, \le \,n - 1} {\;\prod\limits_{1\, \le \,j\, \le \,n - m - 1} {k_{\,j} } } = \\ = n!\sum\limits_{\begin{array}{*{20}c} {0\, \le \,k_{\,j} } \\ {0\, \le \,k_{\,1} + k_{\,2} + \, \cdots \, + k_{\,n} = \,m} \\ {0\, \le \,1\,k_{\,1} + 2\,k_{\,2} + \, \cdots \, + n\,k_{\,n} = \,n\;} \\ \end{array}\;} {\;\prod\limits_{1\, \le \,j\, \le \,n} {\frac{1}{{k_{\,j} !}}\frac{1}{{j^{\,k_{\,j} } }}} } \\ \end{array}$$ The first in particular, the one of your interest, comes from applying the Cauchy product to the exponential generating function $$\left( {\ln \left( {{1 \over {1 - x}}} \right)} \right)^{\,m} = \sum\limits_{0\, \le \,k} {{{m!} \over {k!}}\left[ \matrix{ k \cr m \cr} \right]\,x^{\,k} }$$
The above confirms the asymptotic expression you found for large $$n$$, and clearly you cannot expect it to be "precise" for lower values of $$n$$.
So, concerning your question about possible "operational bounds" for finite $$n,m$$, much depends of course on how you allow the bounds to be expressed and the precision required.
As far as I am aware, there is an interesting precise expression reported in Concrete Mathematics in terms of the Eulerian Numbers of 2nd kind $$\left[ \matrix{ x \cr x - n \cr} \right] = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left\langle {\left\langle \matrix{n \cr k \cr} \right\rangle } \right\rangle \left( \matrix{ x + k \cr 2n \cr} \right)} \quad \quad \left| {\;0 \le n \in Z} \right.$$ which is a polynomial in $$x$$ of degree $$2n$$, that can also be used to extend the definition of the Stirling N. 1st kind to real or complex values of $$x$$.
• Ok, so the problem definitely amounts to estimating Stirling numbers of the first kind... From my research, the typical results you find in the literature are asymptotic expansions of $s(n, n- tn^{\alpha})$ (where $0 < \alpha < 1$ and $t > 0$ are fixed) as $n \to \infty$ but does one know simple operational bounds of $s(n, k)$ for all finite $n, k$ ? – IchKenneDeinenNamen Feb 16 at 12:26