Problem 11164
(American Mathematical Monthly, Vol.112, June-July 2005) Proposed by J. L. D´ıaz-Barrero (Spain).
Show that ifn is a positive integer then
n
X
k=1
(−1)k+1n k
X
1≤i≤j≤k
1 ij = 1
n2.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
We define for k, r ≥ 1
ak,0:= 1, a0,r:= 0, ak,r:= X
1≤i1≤i2≤···≤ir≤k
1 i1i2· · ·ir
(note that ak,1= Hk = 1 + 1/2 + · · · + 1/k is the kth harmonic number).
We will prove the more general identity
n
X
k=1
(−1)k+1n k
ak,r= 1 nr.
For k, r ≥ 1
ak,r=
k
X
ir=1
1 ir
X
1≤i1≤i2≤···≤ir−1≤ir
1 i1i2· · ·ir−1
=
k
X
i=1
ai,r−1
i = ak−1,r+ak,r−1
k .
Therefore for r ≥ 1 we have that
n
X
k=1
(−1)k+1n k
ak,r=
n
X
k=1
(−1)k+1n − 1 k − 1
+n − 1 k
ak,r
=
n
X
k=1
(−1)k+1n − 1 k − 1
h
ak−1,r+ak,r−1
k i+
n−1
X
k=1
(−1)k+1n − 1 k
ak,r
=
n
X
k=1
(−1)k+1n − 1 k − 1
ak−1,r+1 n
n
X
k=1
(−1)k+1n k
ak,r−1+
n−1
X
k=1
(−1)k+1n − 1 k
ak,r
= −
n−1
X
k=0
(−1)k+1n − 1 k
ak,r+1 n
n
X
k=1
(−1)k+1n k
ak,r−1+
n−1
X
k=1
(−1)k+1n − 1 k
ak,r
= a0,r+ 1 n
n
X
k=1
(−1)k+1n k
ak,r−1= 1 n
n
X
k=1
(−1)k+1n k
ak,r−1.
Using the above identity r times we find that
n
X
k=1
(−1)k+1n k
ak,r= 1 nr
n
X
k=1
(−1)k+1n k
ak,0= 1 nr
n
X
k=1
(−1)k+1n k
= 1 nr.
