In this post we denote the Stirling number of the second kind as ${n\brace k}$, I add as reference the article Stirling numbers of the second kind from the encyclopedia Wikipedia. And we denote the sum of divisors function as $\sigma(n)=\sum_{1\leq d\mid n}d$.

I wondered if it is possible to prove some of the following conjectures that I got using a Pari/GP program inspired in an article that refers [1].

Conjecture 1. The estimate $$\frac{1}{n}\sum_{1\leq k\leq n}\frac{\sigma\left({n\brace k}\right)}{{n\brace k}}>C\cdot\log\log\log n$$ holds for all $n\geq 16$, being $C>0$ a suitable constant.

Conjecture 2. One has that $$\frac{\sum_{1\leq k\leq n}\sigma\left({n\brace k}\right)}{n^{4+\frac{n}{2}}}\to\infty$$ as $n\to\infty$.

Question. Is it possible to prove Conjecture 1 or Conjecture 2? Many thanks.

I think that these conjectures aren't more interesting than studied in [1], but I've curiosity about if it can be deduced (from the few computational evidence that I have, my experiments tell me that these conjectures can aren't sharpest). I would like to know what work can be done to elucidate the veracity of our conjectures.


[1] F. Luca, Sums of divisors of binomial coefficients, Int. Math. Res. Not. IMRN (2007), Art. ID rnm 101.

I know it from the introductory section of

Florian Luca and Juan Luis Varona, Multiperfect numbers on lines of the Pascal triangle, Journal of Number Theory, Volume 129, Issue 5 (2009).

  • $\begingroup$ All, is there any idea to prove these conjectures? Do you think that it is possible to improve the statements of my conjectures? $\endgroup$ – user142929 Sep 26 '19 at 10:01

Conjecture 2 seems to be true. If $n \geq 2$ then

$$\frac{1}{2}(k^2+k+2)k^{n-k-1}-1 \leq \left\{{n \atop k}\right\} \leq \frac{1}{2}{n \choose k} k^{n-k} < 2^n k^{n-k}. $$ (Inequalities from Here.)

For a lower bound for your sum we have $$\sum_{1\leq k\leq n}\sigma\left({n\brace k}\right) \geq \sum_{1\leq k\leq n} \frac{1}{2}(k^2+k+2)k^{n-k-1}-1 . $$ Let's try to estimate then $$T(n) = \sum_{1\leq k\leq n} (k^2+k+2)k^{n-k-1}.$$ Note that the function $f(n,x) = x^{n-x}$ has its maximum when $x \approx \frac{n}{\log n}.$ So we'll say that $T(x)$ is at least about $$\frac{n^2}{\log^2 n} \left(\frac{n}{\log n}\right)^{(n- \frac{n}{\log n}-1)} = \frac{n}{\log n} \left(\frac{n}{\log n}\right)^{(n- \frac{n}{\log n})} . $$ One can see by comparing logs that this last grows faster than $n^{c+\frac{n}{2}}$ for any $c$. Notice that we haven't used any properties of $\sigma$ here at all, just bounds on the size of Stirling numbers.

If one does want an idea of the upper bound, we can do a little with that. $\sigma(n) = O(n \log \log n). So, $$\sigma({n\brace k}) =O\left(2^n n^{n-k} \log (n \log 2 + (n-k) \log k) \right) = O(2^n n^{n-k} \log \log n ).$$

$$\sum_{1\leq k\leq n}\sigma\left({n\brace k}\right) = \sum_{1 \leq k \leq n} O(2^n n^{n-k} \log \log n ) = O\left((2^n \log \log n)\sum_{1 \leq k \leq n} n^{n-k}\right). $$

We have that $\sum_{1 \leq k \leq n} n^{n-k} = O(n^{n-1})$, so $$\sum_{1\leq k\leq n}\sigma\left({n\brace k}\right) = O(2^n n^n \log \log n).$$ Since we've engaged in some pretty heavy overestimating here (especially in regards to the binomial coefficients) this should be able to improved a fair bit.

  • $\begingroup$ Many thanks for your great answer, I'm going to read it and study your nice computations. Since I was asking for some of those conjectures I should accept an answer as soon as I understand the computations and reasonings. And as soon I have enough reputation I'm going to upvote for your statement. Many thanks for your attention and patience. $\endgroup$ – user142929 Apr 25 '20 at 19:19

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.