For each non-empty subset of {1, 2, ... , n} take the sum of the elements divided by the product. Show that the sum of the resulting quantities is n2 + 2n - (n + 1)sn, where sn = 1 + 1/2 + 1/3 + ... + 1/n.
Solution
This is a straightforward induction. For n = 1 the only term in the sum is 1/1 with sum 1. The formula gives 12 + 2.1 - 2.1 = 1. So it is true for n = 1.
Note first that for n the sum of the inverses of the products, including 1 for the empty set, is (1 + 1/1)(1 + 1/2)(1 + 1/3) ... (1 + 1/n) = n+1 (it telescopes). Now the sum for n+1 is the sum for n plus the sum of terms involving n+1. But if a term involves n+1, then the sum is increased by n+1 and the product is increased by a factor n+1. So the sum of all the terms involving n+1 is (1/n+1 x sum for n) + (sum of inverse products for n) = (n2 + 2n - (n+1)sn)/(n+1) + (n+1) = n+1 - 1/(n+1) - sn + (n+1) = 2(n+1) - sn+1. Hence the sum for n+1 is (n2 + 2n) - (n+1)sn + 2(n+1) - sn+1 = (n+1)2 + 2(n+1) - 1 - (n+1)sn - sn+1 = (n+1)2 + 2(n+1) - (n+1)/(n+1) - (n+1)sn - sn+1 = (n+1)2 + 2(n+1) - (n+2)sn+1.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002