1991 USAMO Problems/Problem 2
Problem
For any nonempty set of numbers, let and denote the sum and product, respectively, of the elements of . Prove that where "" denotes a sum involving all nonempty subsets of .
Solution
Let denote the set . Since , the empty sum, is equal to zero, and , the empty product, is equal to 1, the equation is equivalent to the desired equation when . We will prove this equation, but first, we prove a lemma.
Lemma. For all nonnegative integers , .
Proof. Evidently, But the terms of this sum are the coefficients of the polynomial , and the sum of the coefficients of this polynomial is as desired.
We now prove our equation by induction on . For , we have the simple equation 0=0.
Suppose the equation holds when . Then By inductive hypothesis, and by the lemma, Since , our equation thus holds by induction. Thus the problem statement is proven.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See Also
1991 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.