Problem 12106
(American Mathematical Monthly, Vol.126, April 2019) Proposed by H. Ohtsuka (Japan).
For any positive integer n, prove
n
X
k=1
n k
X
1≤i≤j≤k
1
ij = X
1≤i≤j≤n
2n− 2n−i ij .
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Solution. Let
An:=
n
X
k=1
n k
X
1≤i≤j≤k
1 ij =
n
X
k=1
n k
k X
j=1
Hj
j and Bn:= X
1≤i≤j≤n
2n− 2n−i ij . where Hj =Pj
i=1 1
i. Then A1= B1= 1. Moreover, for n > 1, An=
n
X
k=1
n− 1 k
+n− 1 k − 1
k X
j=1
Hj
j = An−1+
n
X
k=1
n− 1 k − 1
k−1
X
j=1
Hj
j +
n
X
k=1
n− 1 k − 1
Hk
k
= 2An−1+1 n
n
X
k=1
n k
Hk
and
Bn= 2 X
1≤i≤j≤n−1
2n−1− 2n−1−i
ij +
n
X
i=1
2n− 2n−i
in = 2Bn−1+ 1 n
n
X
i=1
2n− 2n−i
i .
Hence, by induction, for any positive integer n, An= Bn if and only if an = bn where
an:=
n
X
k=1
n k
Hk and bn:=
n
X
i=1
2n− 2n−i
i .
We have that a1= b1= 1. Moreover, for n > 1,
an =
n
X
k=1
n− 1 k
+n− 1 k − 1
Hk = an−1+
n
X
k=1
n− 1 k − 1
Hk−1+
n
X
k=1
n− 1 k − 1
1 k
= 2an−1+1 n
n
X
k=1
n k
= 2an−1+2n− 1 n and
bn= 2
n−1
X
i=1
2n−1− 2n−1−i
i +2n− 2n−n
n = 2bn−1+2n− 1 n .
Therefore, again by induction, for any positive integer n, an= bn and we are done.
