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.
 A: I apologize ahead of time for not being interested in an inductive proof, this just seems simpler to me personally and it's the argument that jumps out to my sensibilities.
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.
A: 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. $$
A: Continue the proof using MI. Assume P(n) is true.
Let $y=a_{n+1}, S=S_n$
Let $f(y)=1+(S+y)+\frac{(S+y)^2}{2!}+...+\frac{(S+y)^{(n+1)}}{(n+1)!}-(1+a_1)(1+a_2)...(1+a_n)(1+y) \quad y>0$
$f'(y)=1+(S+y)+\frac{(S+y)^2}{2!}+...+\frac{(S+y)^{n}}{n!}-(1+a_1)(1+a_2)...(1+a_n)$
$ > 1+S+\frac{S^2}{2!}+...+\frac{S^{n}}{n!}-(1+a_1)(1+a_2)...(1+a_n) \geq 0 $
$f(0) = 1+S+\frac{S^2}{2!}+...+\frac{S^{(k+1)}}{(k+1)!}-(1+a_1)(1+a_2)...(1+a_n)$
$> 1+S+\frac{S^2}{2!}+...+\frac{S^{n}}{n!}-(1+x_1)(1+x_2)...(1+x_n) \geq 0$
Since f is differentiable w.r.t y, thus $f(y) \geq f(0) \geq 0$ for $y>0$
Rewrite $(S+y)$ as $S_{n+1}$ and $y$ as $a_{n+1}$
$1+S_{n+1}+\frac{S_{n+1}^2}{2!}+...+\frac{S_{n+1}^{(n+1)}}{(n+1)!} \geq (1+a_1)(1+a_2)...(1+a_n)(1+a_{n+1})$
Then P(n+1) is also true.
