Problem 11026
(American Mathematical Monthly, Vol.110, August-September 2003) Proposed by J. Sondow (USA).
LetHn denote thenth harmonic number Pn
11/k. Let H0 = 0. Prove that for positive integers n andk with k ≤ n,
k−1
X
i=0 n
X
j=k
(−1)i+j−1n i
n j
1 j − i =
k−1
X
i=0
n i
2
(Hn−i− Hi).
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
We define for i 6= j
aij = (−1)i+j−1n i
n j
1
j − i and bi=n i
2
(Hn−i− Hi).
Since aij= −ajithen
k−1
X
i=0 k−1
X
j=0 j6=i
aij = 0.
So we have to prove that
k−1
X
i=0 n
X
j=k
aij=
k−1
X
i=0 n
X
j=k
aij+
k−1
X
i=0 k−1
X
j=0 j6=i
aij =
k−1
X
i=0 n
X
j=0 j6=i
aij =
k−1
X
i=0
bi.
Therefore it suffices to show that for i = 0, . . . , n
n
X
j=0 j6=i
aij = bi,
that is
X
j=0 j6=i
n j
(−1)j
j − i = (−1)i−1n i
(Hn−i− Hi).
It is well known (see for example the beautiful book Concrete Mathematics of Graham-Knuth- Patashnik) that if f is a function then
∆nf (x) =
n
X
j=0
n j
(−1)jf (x + j).
In particular, when f (x) = 1/x, we obtain
n
X
j=0
n j
(−1)j
x + j = n!
x(x + 1) · · · (x + n) for x 6∈ {0, −1, . . . , −n}.
Hence, letting
Pi(x) =
i−1
Y
j=0
(x + j) and Qi(x) =
n
Y
j=i+1
(x + j)
(note that P0(x) = Qn(x) = 1), we have
n
X
j=0 j6=i
n j
(−1)j
x + j = n!
(x + i) Pi(x) Qi(x)+ (−1)i−1n i
1 x + i
= n! + (−1)i−1 niPi(x) Qi(x) (x + i) Pi(x) Qi(x) .
Now, the result follows by taking in the previous equation the limit as x goes to −i. The limit of the left side is just
n
X
j=0 j6=i
n j
(−1)j j − i.
On the other hand, applying Hˆopital theorem, the limit of the right side is
x→−ilim
n! + (−1)i−1 niPi(x) Qi(x) (x + i) Pi(x) Qi(x)
= limH
x→−i
(−1)i−1 ni D(Pi(x) Qi(x)) Pi(x) Qi(x) + (x + i) D(Pi(x) Qi(x))
= (−1)i−1n i
Pi′(−i)
Pi(−i) +Q′i(−i) Qi(−i)
= (−1)i−1n i
(Hn−i− Hi), because
Pi′(x) Pi(x) =
i−1
X
j=0
1
x + j and Q′i(x) Qi(x) =
n
X
j=i+1
1 x + j
and Pi′(−i)
Pi(−i) = −Hi and Q′i(−i)
Qi(−i) = Hn−i.