Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1991 USAMO Problems/Problem 2

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)} + \sum_{S \subseteq N(a)} \frac{\sigma(S \cup \{a+1\})}{\pi(S \cup \{a+1\})} \\ &= \sum_{S \subseteq N(a)} \frac{\sigma(S)}{\pi(S)} + \sum_{S \subseteq N(a)} \frac{\sigma(S) + (a+1)}{(a+1) \cdot \pi(S)} \\ &= \frac{a+2}{a+1} \sum_{S\subseteq N(a)} \frac{\sigma(S)}{\pi(S)} + \sum_{S \subseteq N(a)} \frac{1}{\pi(S)} . \end{align*} 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+1) \sum_{k=1}^a \frac{1}{k} \right] \\ &= (a+2)(a+1) - \frac{a+2}{a+1} - (a+2) \sum_{k=1}^a \frac{1}{k} \\ &= (a+2)(a+1) - (a+2) \sum_{k=1}^{a+1} \frac{1}{k}, \end{align*} 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.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1991_USAMO_Problems/Problem_2&oldid=79512"