I stumbled upon the following inequality which, I believe, is true. I was able to prove it for small k, but I have no proof for the general case. Any help is welcome.

Let $n\geq k\geq 1$ then $$\left(1+\frac{1}{n}\right)^k S(n+1,k+1)\geq \left(1+\frac{1}{k}\right)^n S(n,k)$$ where $S(n,k)$ is a Stirling number of second kind.

  • $\begingroup$ Temme (Studies in applied mathematics 89, 23-243) gave an asymptotic expression for Stirling numbers. Did you check whether it suffices to yield your inequality, at least for a certain range of $n,k$? $\endgroup$ – Jan-Christoph Schlage-Puchta Feb 12 '17 at 14:48
  • $\begingroup$ this should be very neat, say, for $n=k+2$ many terms of Taylor expansion coincide $\endgroup$ – Fedor Petrov Feb 13 '17 at 10:47

Let me prove a weaker inequality, the proof of which allows further improvements. Note that $S(n,k)=h_{n-k}(1,2,\dots,k)$, where $$h_t(x_1,\dots,x_k)=\sum_{a_1+\dots+a_k=t,a_i\geqslant 0} x_1^{a_1}\dots x_k^{a_k}$$ is a complete symmetric polynomial. Thus $$\frac{S(n+1,k+1)}{S(n,k)}=\frac{h_{n-k}(1,2,\dots,k+1)}{h_{n-k}(1,2,\dots,k)}=\frac{\sum(p_1+1)\dots (p_{n-k}+1)}{\sum p_1\dots p_{n-k}},$$ where summation is taken over $0\leqslant p_1\leqslant p_2\leqslant \dots \leqslant p_{n-k}\leqslant k$. For any such $(n-k)$-tuple we have $$(p_1+1)\dots (p_{n-k}+1)\geqslant \left(1+\frac1k\right)^{n-k}p_1\dots p_{n-k},$$ summing up we get $$S(n+1,k+1)\geqslant \left(1+\frac1k\right)^{n-k} S(n,k),$$ this is worse than you need, but the inequality was not sharp enough. Roughly speaking, you need to prove that "in average" the ratio $(1+1/p_1)\dots (1+1/p_{n-k})$ grows as $(1+2/k)^{n-k}$, that corresponds to "average" $p_i\sim k/2$.


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.