Problem 11274
(American Mathematical Monthly, Vol.114, February 2007)
Proposed by D. Knuth (USA).
Prove that for nonnegative integers m and n
m
X
k=0
2k2m − k m+ n
= 4m−
n
X
j=1
2m + 1 m+ j
.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
m
X
k=0
2k2m − k m+ n
=
m−n
X
k=0
2k2m − k m+ n
=
m−n
X
k=0
k
X
j=0
k j
2m − k m+ n
=
m−n
X
k=0 k
X
j=0
2m − k m+ n
k j
=
m−n
X
j=0 m−n
X
k=j
2m − k m+ n
k j
=
m−n
X
j=0 m−n−j
X
k=0
2m − j − k m+ n
j + k j
=
m−n
X
j=0
2m + 1 m+ n + j + 1
=
m+1
X
j=n+1
2m + 1 m+ j
where we used the binomial identity (see Concrete Mathematics by Graham, Knuth and Patashnik)
l−s
X
k=0
l− k s
q + k t
=l + q + 1 s+ t + 1
for s = m + n, t = q = j, and l = 2m − j. Therefore
m
X
k=0
2k2m − k m+ n
+
n
X
j=1
2m + 1 m+ j
=
m+1
X
j=1
2m + 1 m+ j
=
2m+1
X
j=m+1
2m + 1 j
= 22m+1 2 = 4m.
