Problem 11609
(American Mathematical Monthly, Vol.118, December 2011)
Proposed by M. N. Deshpande (India).
Let n be an integer greater than 1, and let Sk(n) be the family of all subsets of {2, 3, . . . , n} with k elements. Let H(k) =Pk
j=1 1
j. Show that
n−1
X
k=0
(2n + 1 − 2k) X
A⊂Sk(n)
Y
j∈A
1
j = (n + 1)((n + 2) − H(n + 1)).
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
For n ≥ 1 and k ≥ 0, let
T (n, k) = X
A⊂Sk(n)
Y
j∈A
1 j.
Note that T (n, 0) = 1 and T (n, n) = 0. Moreover for k ≥ 1
T (n + 1, k) =T (n, k − 1)
n + 1 + T (n, k).
We show that the identity holds by induction. For n = 1
0
X
k=0
(3 − 2k)T (1, k) = 3 = (1 + 1)((1 + 2) − H(1 + 1)).
Now we assume that
n−1
X
k=0
(2n + 1 − 2k)T (n, k) = (n + 1)((n + 2) − H(n + 1)).
Hence
n
X
k=0
(2(n + 1) + 1 − 2k)T (n + 1, k) = 2n + 3 +
n
X
k=1
(2n + 3 − 2k) T (n, k − 1)
n + 1 + T (n, k)
= 1
n + 1
n
X
k=1
(2n + 1 − 2(k − 1))T (n, k − 1)
+
n−1
X
k=0
(2n + 1 − 2k)T (n, k) + 2
n−1
X
k=0
T (n, k)
=n + 2
n + 1· (n + 1)((n + 2) − H(n + 1)) + 2
n−1
X
k=0
T (n, k)
= (n + 2)((n + 2) − H(n + 1)) + n + 1 = (n + 2)((n + 3) − H(n + 2))
where we used the fact that 2Pn−1
k=0T (n, k) = n + 1 for n ≥ 1, which can be easily verified by
induction.
