1
$\begingroup$

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$?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$ ? $\endgroup$ – IchKenneDeinenNamen Feb 16 at 12:26
  • $\begingroup$ @IchKenneDeinenNamen: added some notes trying to answer to your comment: wish that helps. $\endgroup$ – G Cab Feb 16 at 21:01

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.