6

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.

GovEcon
  • 2,656
  • 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
  • 1
    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

3 Answers3

7

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.

anon
  • 151,657
6

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. $$

0

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.

Abel Wong
  • 1,173