Problem 11103
(American Mathematical Monthly, Vol.111, October 2004) Proposed by G. Galperin and H. Gauchman (USA).
Prove that for every positive integer n,
n
X
k=1
1 k nk =
1 2n−1
n
X
k = 1 k odd
n k
k .
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
We first note that
n
X
k=1
1 k nk =
n
X
k=1
1 n nk−1
−1
= 1 n
n−1
X
k=0
1
n−1 k
= 1 2n ·
n−1
X
k=0
2k+1 k+ 1.
We prove the last equality by induction (see also Problem 1682 of the Magazine). It holds for n= 1. Now take n > 1 and note that for k = 0, . . . , n − 2
1
n−1 k+1
+ 1
n−1 k
=
n k+1
n−1 k+1
·
n−1 k
=
n k+1·
n−1 k
n−1 k+1·
n−2 k
·
n−1 k
= n n − 1·
1
n−2 k
. Then summing over k and using the induction hypothesis we get
n−2
X
k=0
1
n−1 k+1
+
n−2
X
k=0
1
n−1 k
= n n − 1·
n−2
X
k=0
1
n−2 k
= n 2n−1 ·
n−2
X
k=0
2k+1 k+ 1 that is
n−1
X
k=1
1
n−1 k
+
n−2
X
k=0
1
n−1 k
= 2
n−1
X
k=0
1
n−1 k
− 1 − 1 = n 2n−1 ·
n−2
X
k=0
2k+1 k+ 1 and finally
1 n
n−1
X
k=0
1
n−1 k
= 1 2n ·
n−2
X
k=0
2k+1 k+ 1 +1
n = 1 2n ·
n−1
X
k=0
2k+1 k+ 1. On the other hand
1 2n−1 ·
n
X
k = 1 k odd
n k
k = 1
2n
n
X
k=1
n k
Z 1
−1
xk−1dx= 1 2n
Z 1
−1
(1 + x)n− 1
x dx
= 1 2n
Z 2
0
yn− 1
y − 1 dy= 1 2n
n−1
X
k=0
Z 2
0
ykdy= 1 2n ·
n−1
X
k=0
2k+1 k+ 1. Hence
n
X
k=1
1 k nk =
1 2n ·
n−1
X
k=0
2k+1 k+ 1 = 1
2n−1
n
X
k = 1 k odd
n k
k .
