# If $S = x_1 + x_2 + .. + x_n$, Prove that $(1+x_1)(1+x_2)..(1+x_n) \le 1 + S + \frac{S^2}{2!} + .. + \frac{S^n}{n!}$ [duplicate]

Let $x_1, x_2, \ldots ,x_n$ be positive real numbers, and let $$S = x_1 + x_2 + \cdots + x_n.$$

Prove that $$(1+x_1)(1+x_2)\ldots(1+x_n) \le 1 + S + \frac{S^2}{2!} + \cdots + \frac{S^n}{n!}$$

Here's my attempt:

Case 1 : Let $x_1 = x_2= x$ (When all terms are equal)

$LHS = (1+x)(1+x) = 1+2x+x^2$

$RHS = 1+\frac{x+x}{1!}+\frac{(x+x)^2}{2!}=1+2x+\color{blue}{2}x^2$

Hence when all terms are equal, $LHS<RHS$.

Case 2 : $x_1\ne x_2$

$LHS=(1+x_1)(1+x_2)=1+{x_1}{x_2}+(x_1+x_2)$ $RHS=1+ (x_1+x_2)+\frac{(x_1+x_2)^2}{2!} =1+{x_1}{x_2}+(x_1+x_2)+\color{blue}{\left(\frac{x_1^2+x_2^2}{2}\right)}$

Hence when even one term is not equal, $LHS\lt RHS$.

From the two cases, it's clear that under no circumstance $LHS \gt RHS$. And hence the (partial) proof.

Is there any way I can improve my proof? If you look again I've considered only two terms and my intuition tells me that it would apply to the entire range but how do I state it mathematically? Or can you think of a better or more rigorous proof than this?

Thanks again!

## marked as duplicate by Martin R, Lucian, John B, s.harp, NamasteJan 29 '17 at 13:33

• Did you try induction ? – Khosrotash Jan 29 '17 at 6:05
• Your proof is not half rigorous. – Lelouch Jan 29 '17 at 6:14
• $\frac{(x+x)^2}{2!}=2x^2$, not $x^2$. – angryavian Jan 29 '17 at 6:26
• @Khosrotash That was my first try but things got out of hand rather soon! I'll try again. – Macindows Jan 29 '17 at 7:09
• @Lelouch lol. I'm not surprised. Still trying to get my head around the other answers here. – Macindows Jan 29 '17 at 7:09

By $AM-GM$ we have $$(1+x_1)(\dots)(1+x_n) \le (1+ \frac{1}{n}S)^n = \sum_{k=0}^n a_kS^k$$ where $$a_k = \frac{n!}{n^k (n-k)!} \frac{1}{k!}\le \frac{1}{k!}.$$

• The last inequality is backwards. – Fimpellizieri Jan 29 '17 at 6:22
• I fixed it. @Fimpellizieri – SSepehr Jan 29 '17 at 6:31
• Good job! Very elegant. – Fimpellizieri Jan 29 '17 at 6:40
• @SSepehr:I wish I can vote +1000 ! – Khosrotash Jan 29 '17 at 7:00
• I saw this post of yours and it is interesting to note that every other answerer here has a higher reputation while you got the most upvotes. And now yours is the best answer too $\ddot \smile$ – Macindows Jan 29 '17 at 8:18

Hint:

$$\prod_{k=1}^n (1+x_k) \leqslant (1 +S/n)^n = 1 + n \frac{S}{n} + \frac{n(n-1)}{2!} \frac{S^2}{n^2} + \ldots + \frac{n(n-1)\ldots 2\cdot 1}{n!}\frac{S^n}{n^n} \\= 1 + S + \frac{1-1/n}{2!}S^2 + \ldots + \frac{(1-1/n)(1-2/n)\ldots (1 - (n-1)/n)}{n!}S^n$$

• How $$1 + n \frac{S}{n} + \frac{n(n-1)}{2!} \frac{S^2}{n^2} + \ldots\leq 1 + S + \frac{S^2}{2!} + \ldots+\frac{S^n}{n!}$$ – Nosrati Jan 29 '17 at 6:33
• @MyGlasses For example, $\frac{n(n-1)}{n^2} \le \frac{n^2}{n^2}=1$. – angryavian Jan 29 '17 at 6:37
• Your answer elaborates the solution of @SSepehr . Thanks! – Macindows Jan 29 '17 at 7:30

I use this fact :$$(x_1+x_2+x_3...+x_n)^n=\sum_{k_1+k_2+...k_j=n} \dfrac{n!}{k_1!k_2!...}x_1^{k_1}x_2^{k_2}...x_n^{k_j}$$ $$1 \leq 1\\(x_1+x_2...+x_n)\leq S\\(x_1x_2+x_1x_3+...+x_{n-1}x_n) \leq \frac12S^2=\frac12(2(x_1x_2+x_1x_3+...)+(x_1^2+x_2^2+...x_n^2))\\(x_1 x_2x_3+x_1x_2x_4+...)\leq\frac{1}{3!}S^3=\frac{1}{6}(\color{red} {\frac{3!}{1!1!1!}(x_1x_2x_3+x_1x_2x_4+...)}+\frac{3!}{2!1!}(x_1^2x_2+x_2^2x_1+...)+\frac{3!}{3!}(x_1^3+x_2^3+...+x_n^3))\\$$

$$(x_1 x_2x_3x_4+x_1x_2x_3x_5+...)\leq\frac{1}{4!}S^4=\frac{1}{24}(\color{red} {\frac{34!}{1!1!1!1!}(x_1x_2x_3x_4+x_1x_2x_3x_5+...)}+\frac{4!}{3!1!}(x_1^3x_2+x_2^3x_1+...)+\frac{4!}{2!2!}(x_1^2x_2^2+...)+\frac{4!}{4!}(x_1^4+x_2^4+...+x_n^4))$$ and so on

now we have $$1\leq1\\+(x_1+x_2+...x_n)\leq\frac{1}{2!}S^2\\ +(x_1x_2+x_1x_3+...)\leq\frac{1}{3!}S^3\\ +(x_1x_2x_3+x_1x_2x_4+...)\leq\frac{1}{4!}S^4\\+...\\ +(x_1x_2x_3...x_n)\leq\frac{1}{n!}S^n\\ 1+(x_1+x_2+...x_n)+(x_1x_2+x_1x_3+...)+...(x_1x_2...x_n)\leq 1+s+\frac{S^2}{2}+...+\frac{S^n}{n!}\\$$ and $$(1+x_1)(1+x_2)...(1+x_n)=1+(x_1+x_2+...x_n)+(x_1x_2+x_1x_3+...)+...(x_1x_2...x_n)$$proof is complete now

• You're solution is longer than the others but this is the only one I understood without much difficulty. Thanks! – Macindows Jan 29 '17 at 7:24
• The fact that I used to prove was expanding the expressions. Your welcome .I think the nice proof was from Ssepehr – Khosrotash Jan 29 '17 at 11:49

By the multinomial theorem, we have that

$$S^m=\sum_{k_1+k_2+\dots+k_n=m}\left(\array{m\\k_1,k_2,\dots,k_n}\right) x_1^{k_1}x_2^{k_2}\dots x_n^{k_n},$$

where the sum is over nonnegative integer $k_i$. Hence, the RHS may be written as:

$$\sum_{m=0}^n\frac{S^m}{m!}=\sum_{k_1+k_2+\dots+k_n\leq n}\frac{1}{k_1!k_2!\dots k_n!}x_1^{k_1}x_2^{k_2}\dots x_n^{k_n}$$

In particular, the monomials all have positive coefficients, and for any monomial with $k_i$ all $\leq 1$, the coefficient is $1$.

On the LHS, it's easy to see that any monomial with $k_i$ all $\leq 1$ can be obtained in exactly one way from the product of $(1+x_i)$'s, and that its coefficient is also $1$. Moreover, no monomial from the expansion of the LHS may have some $k_i>1$. The conclusion follows (because the RHS has some 'extra' monomials).

EDIT: Notice this also shows that there never is equality when $n>1$. Indeed, even in your question you made a mistake. When $x_1=x_2=x$, we have $\frac{(x+x)^2}{2!}=2x^2$.

• I think you forgot $m!$ in second formula – Khosrotash Jan 29 '17 at 6:58
• The $m!$ from the multinomial theorem (in the numerator) cancels out with the $\frac{1}{m!}$ from the RHS. I will edit to make it more explicit. – Fimpellizieri Jan 29 '17 at 7:02
• @Fimpellizieri Yes I noticed the mistake! Thanks for the solution. – Macindows Jan 29 '17 at 7:32