Problem 11832
(American Mathematical Monthly, Vol.122, April 2015) Proposed by D. Knuth (USA).
Let C(z) be the generating function of the Catalan numbers. Prove that
(log(C(z)))2=
∞
X
n=1
2n n
(H2n−1− Hn)zn n, where Hk =Pk
j=11/j is the k-th harmonic number.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
We note that
∞
X
n=1
2n n
zn n =
Z z 0
∞
X
n=1
2n n
xn−1dx = Z z
0
1
√1 − 4x− 1 dx x
= Z 1
1−4z
1
√t − 1
dt 1 − t =
Z 1 1−4z
√ 1 t(1 +√
t)dt
=h
2 ln(1 +√ t)i1
1−4z
= 2 log(C(z)).
Hence
(log(C(z)))2= 1 4
∞
X
n=1 n−1
X
k=1
1
k(n − k)
2k k
2(n − k) n − k
zn
= 1 4
∞
X
n=1 n−1
X
k=1
1 k+ 1
n − k
2k k
2(n − k) n − k
zn n
= 1 2
∞
X
n=1 n−1
X
k=1
1 k
2k k
2(n − k) n − k
zn n. Therefore, it suffices to show by induction that
n−1
X
k=1
F (n, k) = 2(H2n−1− Hn) where F (n, k) = 1 k
2k k
2(n − k) n − k
2n n
−1
.
It holds for n = 1, and it is easy to verify that
F (n + 1, k) − F (n, k) = G(n, k + 1) − G(n, k) where G(n, k) = − k2(2n − 2k + 1)F (n, k) (n + 1)(2n + 1)(n + 1 − k). Hence, by the inductive assumption,
n
X
k=1
F (n + 1, k) =
n
X
k=1
F (n, k) +
n
X
k=1
(G(n, k + 1) − G(n, k))
= 2(H2n−1− Hn) + F (n, n) + G(n, n + 1) − G(n, 1)
= 2(H2n−1− Hn) +1
n + 0 + (2n − 1)F (n, 1) (n + 1)(2n + 1)n
= 2(H2n−1− Hn) +1
n + 1
(n + 1)(2n + 1) = 2(H2n+1− Hn+1).
