AoPSWiki
Trying to get to the USAMO in 2010? Our AIME Problem Series can help you get there! Click here to enroll today!

1991 USAMO Problems/Problem 2

From AoPSWiki

Problem

For any nonempty set \,S\, of numbers, let \,\sigma(S)\, and \,\pi(S)\, denote the sum and product, respectively, of the elements of \,S\,. Prove that \sum \frac{\sigma(S)}{\pi(S)} = (n^2 + 2n) - \left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \right) (n+1), where "\Sigma" denotes a sum involving all nonempty subsets S of \{1,2,3, \ldots,n\}.

Solution

Let N(m) denote the set \{1, \dotsc, m\}. Since \sigma(\varnothing), the empty sum, is equal to zero, and \pi(\varnothing), the empty product, is equal to 1, the equation \sum_{S \subseteq N(n)} \frac{\sigma(S)}{\pi(S)} = (n+1)^2 -1 - (n+1)\sum_{k=1}^n \frac{1}{k} is equivalent to the desired equation when n >0. We will prove this equation, but first, we prove a lemma.

Lemma. For all nonnegative integers n, \sum_{S \subseteq N(n)} \frac{1}{\pi(S)} = n+1.

Proof. Evidently, \sum_{S \subseteq N(n)} \frac{1}{\pi(S)} = \sum_{k=0}^n \sum_{S \subseteq N(n), |S| =k} \frac{1}{\pi(S)} . But the terms of this sum are the coefficients of the polynomial P(x) = \prod_{k=1}^n (x + 1/k), and the sum of the coefficients of this polynomial is P(1) = \prod_{k=1}^n(1 + 1/k) = \prod_{k=1}^n \frac{k+1}{k} = \frac{n+1}{1} = n+1, as desired. \blacksquare

We now prove our equation by induction on n. For n=0, we have the simple equation 0=0.

Suppose the equation holds when n=a. Then \begin{align*}\sum_{S \subseteq N(a+1)} \frac{\sigma(S)}{\pi(S)} &= \sum_{S \subseteq N(a)} \frac{\sigma(S)}{\pi(S)} + \s... By inductive hypothesis, \begin{align*}\frac{a+2}{a+1} \sum_{S \subseteq N(a)} \frac{\sigma(S)}{\pi(S)} &= \frac{a+2}{a+1} \left[ (a+1)^2 -1 - (a+... and by the lemma, \sum_{S \subseteq N(a)} \frac{1}{\pi(S)} = a+1 . Since (a+2)(s+1) = (a+3)(a+1) = (a+2)^2 -1, our equation thus holds by induction. Thus the problem statement is proven. \blacksquare


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

1991 USAMO (Problems)
Preceded by
Problem 1 		1 • 2 • 3 • 4 • 5 Followed by
Problem 3
All USAMO Problems and Solutions
Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/1991_USAMO_Problems/Problem_2"
Want to learn how to tackle those tough MATHCOUNTS and AMC counting and probability problems? Check out Art of Problem Solving's Introduction to Counting & Probability by David Patrick.
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us