Problem 11928
(American Mathematical Monthly, Vol.123, August-September 2016)
Proposed by H. Ohtsuka (Japan).
For positive integers n and m and for a sequence{ai}i≥1, prove
n
X
i=0 m
X
j=0
n i
m j
ai+j =
n+m
X
k=0
n + m k
ak
and
X
0≤i<j≤n
n i
n j
i + j n
= X
0≤i<j≤n
n i
n j
2 .
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Solution. The first identity is a simple application of Vandermonde’s identity,
[zn+m](z + 1)n· (z + 1)m· f (z) =
n
X
i=0 m
X
j=0
n n− i
m m− j
ai+j =
n
X
i=0 m
X
j=0
n i
m j
ai+j
and
[zn+m](z + 1)n+m· f (z) =
n+m
X
k=0
n+ m n+ m − k
ak =
n+m
X
k=0
n + m k
ak
where f (z) :=P
k≥0akzk.
As regards the second identity, we have to show that Ln= Rn where
Ln:= X
0≤i<j≤n
n i
n j
i + j n
= X
0≤j<i≤n
n i
n j
i + j n
,
and
Rn:= X
0≤i<j≤n
n i
n j
2
= X
0≤j<i≤n
n n− i
n n− j
2
= X
0≤j<i≤n
n i
n j
2 .
Let m = n and ak = kn in the first one, then
n
X
i=0
n i
22i n
+2Ln=
n
X
i=0 n
X
j=0
n i
n j
i + j n
=
2n
X
k=0
2n k
k n
=2n n
2n X
k=n
n k− n
= 2n·2n n
.
Moreover
n
X
i=0
n i
3
+ 2Rn=
n
X
i=0
n i
!
·
n
X
j=0
n j
2
= 2n·2n n
.
Therefore, it suffices to prove that
n
X
i=0
n i
3
=
n
X
i=0
n i
22i n
which is known as Strehl’s identity. For the sake of completeness, we give a short proof below:
n
X
i=0
n i
3
=
n
X
i=0
n i
n n− i
i X
k=0
i i− k
n − i k
=
n
X
k=0
n k
2 n X
i=k
n − k i
n − k n− i
=
n
X
k=0
n k
22(n − k) n
=
n
X
k=0
n n− k
22k n
=
n
X
k=0
n k
22k n
.