Problem 11007
(American Mathematical Monthly, Vol.110, April 2003) Proposed by Western Maryland College Problems Group (USA).
Let denote Eulerian numbers, and let denote Stirling numbers of the second kind. Show that
n
X
j=1
2j−1 n j
=
n
X
j=1
j!n j
.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
We will prove these two equalities by induction on n ≥ 1:
n
X
j=1
n j
xn+1−j (1 − x)n+1 =
∞
X
j=1
jnxj =
n
X
j=1
j!n j
xj
(1 − x)j+1 for |x| < 1.
The wanted identity follows taking x = 12. We start with the first one. Since 1
1 = 1 and (1−x)x 2 = P∞
j=1jnxj then the equality holds for n= 1. Moreover, for n ≥ 1 we have that
∞
X
j=1
jn+1xj = x· d dx
∞
X
j=1
jnxj
= x · d dx
n
X
j=1
n j
xn+1−j (1 − x)n+1
= x·
n
X
j=1
n j
(n + 1 − j) xn−j
(1 − x)n+1 + (n + 1) xn+1−j (1 − x)n+2
=
n
X
j=1
n j
(n + 1 − j)xn+1−j(1 − x)
(1 − x)n+2 + (n + 1) xn+2−j (1 − x)n+2
=
n
X
j=1
n j
(n + 1 − j) xn+1−j
(1 − x)n+2 + j xn+2−j (1 − x)n+2
=
n+1
X
j=2
(n + 2 − j)
n j− 1
xn+2−j (1 − x)n+2 +
n
X
j=1
j n j
xn+2−j (1 − x)n+2
=
n+1
X
j=1
n + 1 j
xn+2−j (1 − x)n+2.
The last equality holds because Eulerian numbers satisfy the following recurrence relation (see for example the On-Line Encyclopedia of Integer Sequences):
n 1
= n n
= 1 and n + 1 j
= (n + 2 − j)
n j− 1
+ j n
j
for j = 2, . . . , n.
Now the second one. Since 1
1 = 1 and (1−x)x 2 = P∞
j=1jnxj then the equality holds for n = 1.
Moreover, for n ≥ 1 we have that
∞
X
j=1
jn+1xj = x · d dx
∞
X
j=1
jnxj
= x · d dx
n
X
j=1
j!n j
xj (1 − x)j+1
= x ·
n
X
j=1
n j
j! j xj−1
(1 − x)j+1 + j ! (j + 1) xj (1 − x)j+2
=
n
X
j=1
n j
j! j xj
(1 − x)j+1 + (j + 1) ! xj+1 (1 − x)j+2
=
n
X
j=1
j! jn j
xj (1 − x)j+1 +
n+1
X
j=2
j!
n j− 1
xj (1 − x)j+1
=
n+1
X
j=1
j!n + 1 j
xj (1 − x)j+1.
The last equality holds because Stirling numbers of the second kind satisfy the following recurrence relation:
n 1
=n n
= 1 and n + 1 j
= jn j
+
n j− 1
for j = 2, . . . , n.
