Problem 12156
(American Mathematical Monthly, Vol.127, January 2020) Proposed by H. Ohtsuka (Japan).
For positive integers m and n and nonnegative integers r and s, prove X
0≤j1≤···≤jm≤r n+s
n
n+j1
n
s+j1
s
Qm
i=1(n + ji) = X
0≤j1≤···≤jm≤s n+r
n
n+j1
n
r+j1
r
Qm
i=1(n + ji) .
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Solution. We first show, by induction with respect to m, that X
0≤j1≤···≤jm≤s n+j1
n
j1
k
Qm
i=1(n + ji) =
n+s n
s k
(n + k)m (1)
where k is a non-negative integer. Let Fs(m, n, k) be the left-hand side.
Base case: if m = 1 then
Fs(1, n, k) = X
0≤j1≤s n+j1
n
j1
k
(n + j1) = X
0≤j1≤s n+j1
n
j1
k
− n+jn1−1
j1−1 k
n+ k =
n+s n
s k
(n + k) . Inductive step: for m > 1,
Fs(m, n, k) =
s
X
t=0
(Ft(m, n, k) − Ft−1(m, n, k)) =
s
X
t=0
Ft(m − 1, n, k) n+ t
=
s
X
t=0
(n+tn )(tk)
(n+k)m−1
n+ t = Fs(1, n, k) (n + k)m−1 =
n+s n
s k
(n + k)m.
Let R(m, n, r, s) be the right-hand side of the given identity, then we have to prove that R(m, n, s, r) = R(m, n, r, s).
Since by Vandermonde’s identity,
r + j1
r
=
r
X
k=0
r r − k
j1
k
=
r
X
k=0
r k
j1
k
,
by using (1), we find
R(m, n, r, s) = X
0≤j1≤···≤jm≤s n+r
n
n+j1
n
Pr k=0
r k
j1
i
Qm
i=1(n + ji)
=n + r n
r X
k=0
r k
X
0≤j1≤···≤jm≤s n+j1
n
j1
k
Qm
i=1(n + ji)
=n + r n
r X
k=0
r k
·
n+s n
s k
(n + k)m
=n + r n
n + s n
min(r,s) X
k=0 r k
s k
(n + k)m
which is symmetric with respect to r and s and we are done.