Proof of an inequality by induction: $(1 + x_1)(1 + x_2)...(1 + x_n) \ge 1 + x_1 + x_2 + ... + x_n$

Let $n \in \mathbb N^+$. Show that if $x_1, x_2, ... , x_n$ are $n$ real numbers such that $-1 \le x_i \le 0$ for each $1 \le i \le n$, then $$(1 + x_1)(1 + x_2)...(1 + x_n) \ge 1 + x_1 + x_2 + ... + x_n$$

I am using a proof by induction, but I am unable to complete it. I would appreciate any tips on how I could finish the proof.

Incomplete Proof
Let $P(n)$ be the proposition that $(1 + x_1)(1 + x_2)...(1 + x_n) \ge 1 + \sum_{i = 1} ^ n x_i$.
When $n = 1$, LHS = RHS = $1 + x_i$. Clearly $1 + x_i \ge 1 + x_i$ and so $P(1)$ is true.
Assume that $P(k)$ is true, i.e. $(1 + x_1)(1 + x_2)...(1 + x_k) \ge 1 + \sum_{i=1}^k x_i$.
Case 1
Suppose $x_{k + 1} = -1$.
Then $1 + x_{k + 1} = 0$, hence LHS = $(1 + x_1)(1 + x_2)...(1 + x_k)(1 + x_{k+1}) = 0$.
RHS = $1 + x_1 + x_2 + ... + x_k - 1 = x_1 + x_2 + ... + x_k$ which is always nonpositive since each $x_i$ is nonpositive.
Hence RHS $\le 0$ and so LHS $\ge$ RHS.
Case 2
Suppose $x_{k+1} = 0$.
Then $1 + x_{k+1} = 1$, hence multiplying it to LHS does not change anything.
Also, adding $x_{k+1}$ to RHS does not change anything.
Therefore, LHS $\ge$ RHS still holds.
Case 3
Suppose $-1 < x_{k+1} < 0$.
Then $0 < 1 + x_{k+1} < 1$.
Adding $x_{k+1}$ to RHS makes the RHS smaller since $x_{k+1}$ is negative.
If LHS $= 0$, then multiplying $1 + x_{k+1}$ to LHS does not change anything, and so LHS $\ge$ RHS holds.
If LHS > $0$, then multiplying $1 + x_{k+1}$ to LHS makes the LHS smaller since $0 < 1 + x_{k+1} < 1$.
In this case LHS $\ge$ RHS does not necessarily hold?
...

We know that

$$(1+x_1)\cdots(1+x_n) \geq 1+x_1+\ldots +x_n$$

If we now multiply the inequality above by $(1+x_{n+1}) \geq 0$ we obtain

$$(1+x_1)\cdots(1+x_n)(1+x_{n+1}) \geq (1+x_1+\ldots +x_n)(1+x_{n+1})\\= (1+x_1+\ldots +x_n) + x_{n+1} + x_{n+1}(x_1+\ldots +x_n) \geq 1 + x_1 + \ldots + x_{n+1}$$

where the last inequality follows from the fact that $x_i \leq 0$ which implies $x_{n+1}(x_1+\ldots +x_n) \geq 0$.

Why not directly instead of cases?

$$\prod_{k=1}^n(1+x_k)=\prod_{k=1}^{n-1}(1+x_k)\cdot(1+x_n)\stackrel{\text{ind. hyp.}\,+\,(1+x_n)\ge0}\ge(1+x_1+\ldots+x_{n-1})(1+x_n)=$$

$$=1+\sum_{k=1}^n x_k+\sum_{k=1}^{n-1}\overbrace{x_kx_n}^{\ge 0}\ge1+\sum_{k=1}^n x_k$$

and we're done

There's no need for induction. Note that when you start increasing any $x_i$, the left side increases slower (or equally) because the product of the other factors besides $(x_i+1)$ is less or equal to $1$. So without loss of generality, all the variables are $0$ and the inequality holds.

• Your method is an elegant one but it's not correct to claim that there is no induction. You need induction to actually prove that you can apply your method to all the (arbitrarily many) variables unless $n$ is already known in advance, and even in that case not having induction would mean that you need to write a proof of length proportional to $n$! Jan 25 '15 at 11:44
• @user21820 There isn't. Find the lowest $\sum x_i$ such that the inequality still holds. Contradiction if it's not everything we want :P On a more serious note, what I mean by that is that you don't need to do the obvious inductive argument using the previous inequality because it's clear from the beginning by considering the linearity. Jan 25 '15 at 12:28
• I don't know if you're joking but there isn't necessarily a lowest sum that you're looking for as it could be an infimum not attained. Jan 25 '15 at 12:39
• @user21820 It obviously must be attained by compactness. The inequality isn't sharp. Jan 25 '15 at 13:57
• Yes of course, but you didn't mention compactness! Those who know all that already won't need your answer and those who don't won't understand your comment correctly if compactness wasn't mentioned. Jan 25 '15 at 14:02

Proof:

When $$n=1$$, it's obvious that $$1+x_1 \geqslant 1+x_1$$ holds.

Suppose $$(1+x_1)(1+x_2)\ldots{}(1+x_k) \geqslant 1+x_1+x_2+\ldots{}+x_k$$ holds when $$n=k$$.

\begin{align} (1+x_1)(1+x_2)\ldots{}(1+x_k)(1+x_{k+1}) &= (1+x_{k+1})\Big[(1+x_1)(1+x_2)\ldots{}(1+x_k)\Big] \\ &\geqslant (1+x_{k+1})(1+x_1+x_2+\ldots{}+x_k) \\ &=1 + x_{k+1} + (x_1+x_2+\ldots{}+x_k) + x_{k+1}(x_1+x_2+\ldots{}+x_k) \end{align}

Because $$x_1,x_2,\ldots{},x_n \in [-1,0]$$, $$\forall i, j \in \{1,2,\ldots{},n\} :\: x_i x_j \geqslant 0$$ $$x_{k+1}(x_1+x_2+\ldots{}+x_k) \geqslant 0$$

Furthermore, \begin{align} (1+x_1)(1+x_2)\ldots{}(1+x_k)(1+x_{k+1}) &\geqslant 1 + x_{k+1} + (x_1+x_2+\ldots{}+x_k) + x_{k+1}(x_1+x_2+\ldots{}+x_k) \\ &\geqslant 1 + x_1 + x_2 + \ldots{} + x_k + x_{k+1} \end{align}

Therefore, for all $$n \in \mathbb{N}^{+}$$, the proposition is always true.

Q.E.D.

Reference: