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^{k}S(n, k) ≥ k^{n}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}

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^{J}fk(J)

≥n k

(k + 1)^{N}fk

1
(k + 1)^{N}

N

X

J =0

N J

k^{J}J

!

=n k

(k + 1)^{N}fk

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}
(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^{J}J = kN
k+ 1.

Therefore the proof of the induction step is complete.