APMO 1989

Let ${\sigma }_k$ be the $k$th symmetric polynomial, namely $${\sigma }_k=\sum _{\begin{array}{c}|S|=k\\ S\subseteq \{1,2,\dots ,n\}\end{array}}\prod _{i\in S}{x}_i,$$ and more explicitly $${\sigma }_1=S,{\sigma }_2=x_1{x}_2+x_1{x}_3+\cdots +x_{n-1}{x}_n,\text{and so on.}$$ Then $$\left(1+x_1\right)\left(1+x_2\right)\cdots \left(1+x_n\right)=1+{\sigma }_1+{\sigma }_2+\cdots +{\sigma }_n.$$ The expansion of $$S^k={\left(x_1+x_2+\cdots +x_n\right)}^k=\underset{k\text{ times }}{\underbrace{\left(x_1+x_2+\cdots +x_n\right)\left(x_1+x_2+\cdots +x_n\right)\cdots \left(x_1+x_2+\cdots +x_n\right)}}$$ has at least $k!$ occurrences of ${\prod }_{i\in S}{x}_i$ for each subset $S$ with $k$ indices from $\{1,2,\dots ,n\}$. In fact, if $\pi$ is a permutation of $S$, we can choose each $x_{\pi (i)}$ from the $i$th factor of ${\left(x_1+x_2+\cdots +x_n\right)}^k$. Then each term appears at least $k!$ times, and $$S^k\ge k!{\sigma }_k⟺{\sigma }_k\le \frac{S^k}{k!}.$$ Summing the obtained inequalities for $k=1,2,\dots ,n$ yields the result.

By AM-GM, $$\left(1+x_1\right)\left(1+x_2\right)\cdots \left(1+x_n\right)\le {\left(\frac{\left(1+x_1\right)+\left(1+x_2\right)+\cdots +\left(1+x_n\right)}{n}\right)}^n={\left(1+\frac{S}{n}\right)}^n.$$ By the binomial theorem, $${\left(1+\frac{S}{n}\right)}^n=\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right){\left(\frac{S}{n}\right)}^k=\sum _{k=0}^n\frac{1}{k!}\frac{n(n-1)\dots (n-k+1)}{n^k}{S}^k\le \sum _{k=0}^n\frac{S^k}{k!},$$ and the result follows.