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$?
 A: That's part of an interesting set of identities involving the (unsigned) Stirling Number of 1st kind
$$
\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$.
