8
$\begingroup$

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\cdot S(n+1,k+1)\,\ \geq \,\ \left(1+\frac{1}{k}\right)^n\cdot S(n,k)$$ where $S(n,k)$ is a Stirling number of second kind.

$\endgroup$
2
  • 1
    $\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$ Feb 12, 2017 at 14:48
  • $\begingroup$ this should be very neat, say, for $n=k+2$ many terms of Taylor expansion coincide $\endgroup$ Feb 13, 2017 at 10:47

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.