• Non ci sono risultati.

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

N/A
N/A
Protected

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

Copied!
1
0
0

Testo completo

(1)

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

nkS(n, k) ≥ kn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 +xkk implies fk′′(x) = 1 +k1

1 +xk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

 kj jk =n

k

 N X

J =0

N J



kJfk(J)

≥n k



(k + 1)Nfk

1 (k + 1)N

N

X

J =0

N J

 kJJ

!

=n k



(k + 1)Nfk

 kN k+ 1



=n k

 (k + 1)N

1 + k+1N 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



kJ= 1, and 1 (k + 1)N

N

X

J =0

N J



kJJ = kN k+ 1.

Therefore the proof of the induction step is complete. 

Riferimenti

Documenti correlati

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit` a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy. Let a(n, k) be the number

For positive integer n and i ∈ {0, 1}, let D i (n) be the number of derangements on n elements whose number of cycles has the same parity

[r]

[r]

(American Mathematical Monthly, Vol.118, February 2011) Proposed by Mihaly Bencze (Romania). For a positive integer k, let α(k) be the largest odd divisor

, 2n} with n cycles all of length greater than 1, that is with all cycles of

in such a way that U 1 receives at least one ball, and while any balls remain, each successive urn receives at least as many balls as in all the previous urns combined.. Let b(n)

[r]