We will show that the inequality holds for n ≥ k ≥ 1 by double induction

Problem 11957

(American Mathematical Monthly, Vol.124, February 2017) Proposed by E. Pit´e (France).

Let k and n be two integers with n ≥ k ≥2. Let S(n, k) be the Stirling number of the second kind, i.e., the number of ways to partition a set of n objects into k nonempty subsets. Show that

n^kS(n, k) ≥ kⁿn k

 .

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

Solution. We will show that the inequality holds for n ≥ k ≥ 1 by double induction.

Basic step: since S(n, 1) = n then the inequality holds trivially for n ≥ k = 1.

Assume now that n ≥ k ≥ 1. Note that the following function is convex: for x > 0,

fk(x) := 1

1 +^x_k
^k implies f_k^′′(x) = 1 +_k¹

1 +^x_k
^k+2 >0.

By a known identity, by the induction hypothesis, and by the convexity of fk, we have

S(n + 1, k + 1) =

n

X

j=k

n j



S(j, k) ≥

n

X

j=k

n j

j k

 k^j j^k =n

k

 ^N X

J =0

N J



k^Jfk(J)

≥n k



(k + 1)^Nfk

1 (k + 1)^N

N

X

J =0

N J

 k^JJ

!

=n k



(k + 1)^Nfk

 kN k+ 1



=n k

 (k + 1)^N

1 + _k+1^N ^k =n k

 (k + 1)^{N +k}

(N + k + 1)^k =n + 1 k+ 1

 (k + 1)ⁿ⁺¹ (n + 1)^k+1

where N = n − k, J = j − k, and it can be easily verified that 1

(k + 1)^N

N

X

J =0

N J



k^J= 1, and 1 (k + 1)^N

N

X

J =0

N J



k^JJ = kN k+ 1.

Therefore the proof of the induction step is complete.