# Prove that: $(1+a_1)(1+a_2)…(1+a_n) \le 1 + S_n + (S_n)^2/2! + … + (S_n)^n/n!$

I am currently working on this problem from Hardy's Course of Pure Mathematics and have gotten stuck near the end. I was wondering if someone could help me determine what to go next.

Question

If $a_1, a_2, ...,a_n$ are all positive and $S_n=a_1+a_2+...+a_n$ then:

$(1+a_1)(1+a_2)...(1+a_n) \le 1 + S_n + \dfrac{(S_n)^2}{2!} + ... + \dfrac{(S_n)^n}{n!}$

My Attempt

Proof by induction:

I had first shown that it was true for $n=1$ and $n=2$.

Now suppose that it is true for n. Then it must also be true for $n+1$

$(1+a_1)(1+a_2)...(1+a_n)(1+a_{n+1}) \le 1 + S_n + \dfrac{(S_n)^2}{2!} + ... + \dfrac{(S_n)^n}{n!} + \dfrac{(S_{n})^{n+1}}{(n+1)!}$

Define: $(1+a_1)(1+a_2)...(1+a_n)=x$ and $1 + S_n + \dfrac{(S_n)^2}{2!} + ... + \dfrac{(S_n)^n}{n!}=y$

Then: $x+xa_{n+1} \le y+\dfrac{(S_{n})^{n+1}}{(n+1)!}$

By the induction assumption, we know that $x \le y$.

What I can't figure out

From this point, what I think the next natural step would be is to show that

$xa_{n+1} \le \dfrac{(S_{n})^{n+1}}{(n+1)!}$

I know this rearranges to:

$xa_{n+1} \le \dfrac{(S_{n})^{n}}{n!} \times \dfrac{S_n}{(n+1)}$

And feel there may be something I can do here, but haven't been able to figure anything out.

• The first inequality in "My Attempt" has a strange right-hand side. Only the last term matches what you get when you substitute $n+1$ into the hypothesis to be proven. Similarly in your bottommost inequality you seem to confuse $S_n$ with $S_{n+1}$. – Erick Wong Mar 10 '13 at 19:38
• Typo - thanks for pointing them out – GovEcon Mar 10 '13 at 21:08
• I wouldn't call it a typo, it's more like you are trying to prove something strictly stronger than what is needed. You only need to prove the bound with $S_{n+1}$ but you're forcing yourself to prove the smaller bound with $S_n$, which might not even be true. In a sense you've fixed the typos in the wrong direction :). – Erick Wong Mar 10 '13 at 21:26

It suffices to show that every monomial on the left (viewed simply as a polynomial on both sides of the equation) also appears on the right, since everything here is positive. For each $k$ and each string of distinct indices $i_1,\cdots,i_k$, the expansion of $S_n^k$ will have $k!$ copies of $a_{i_1}\cdots a_{i_k}$ corresponding to all the possible ways of ordering the terms, so when the coefficient $k!$ is divided by $k!$ it will be $1$, and so every monomial on the left also appears on the right.
The AMGM inequality immediately gives the stronger bound $$(1+a_1)(1+a_2)\cdots(1+a_n) \leq \left(1+{S_n\over n}\right)^n.$$