1991 USAMO Problems/Problem 2
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 .
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.
|1991 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|