Want Some Hint on a Proof of an Inequality by Induction

Question

The problem comes from a problem sheet of an introductory math course by Oxford. It is question 1 in https://courses.maths.ox.ac.uk/node/download_material/45907. I don't study there I'm just curious and want to try.

Given $n$ positive numbers $x_1, x_2,\ldots,x_n$ such that $x_1+x_2+\ldots+x_n\le 1/3$, prove by induction that
$$(1-x_1)(1-x_2)\cdot\ldots\cdot(1-x_n)\ge 2/3.$$

My attempt:
For $n=1$,
$$x_1\le1/3$$ $$-x_1\ge-1/3$$ $$1-x_1\ge1-1/3$$ $$1-x_1\ge2/3$$

(Incorrect)
Assume $(1-x_1)(1-x_2)\cdot\ldots\cdot(1-x_k)\ge2/3$ for some $k$.
For $n=k+1$,
$$ \left\{ \begin{array}{c} x_1+x_2+\ldots+x_k\le1/3\qquad(1)\\ x_1+x_2+\ldots+x_k+x_{k+1}\le1/3\qquad(2) \end{array} \right. $$ $(2)-(1):$ $$x_{k+1}\le0$$ $$-x_{k+1}\ge0$$ $$1-x_{k+1}\ge1$$ Then$$(1-x_1)(1-x_2)\cdot\ldots\cdot(1-x_k)(1-x_{k+1})$$ $$\ge2/3\cdot1$$ $$\ge2/3$$ But it looks like a paradox because $(1)$ and $(2)$ can't be true at the same time. For $n>1$, I cannot make the given inequality into the desired one. They are just not equivalent.

I'm looking for a hint. Sorry but I think they are not grading it now. Thank you.

Edit:
Reply to Kavi Rama Murthy:
When $n=2$, $$x_1+x_2\le1/3$$ $$1-x_1-x_2\ge2/3$$ Then $$(1-x_1)(1-x_2)=1-x_1-x_2+x_1x_2$$ $$\ge(2/3)+x_1x_2$$ $$\ge2/3$$
For $n=k+1$, given that $$x_1+x_2+...+x_k+x_{k+1}\le1/3$$ and apply the $n=k$ case with $x_1,x_2,...,x_k+x_{k+1}$, $$(1-x_1)(1-x_2)\cdot\ldots\cdot(1-x_k-x_{k+1})$$ $$=(1-x_1)(1-x_2)\cdot\ldots\cdot[(1-x_k)(1-x_{k+1})-x_kx_{k+1}]\ge2/3$$ Then $$(1-x_1)(1-x_2)\cdot\ldots\cdot(1-x_k)(1-x_{k+1})\ge2/3+x_kx_{k+1}(1-x_1)(1-x_2)\cdot\ldots\cdot(1-x_k)$$ $$\ge2/3$$
Reply to ΑΘΩ:

(Replaced with the empty $I$ case)
When $I$ has $1$ element, $${\displaystyle \prod_{i\in I}^{1} (1-x_i)}=1-x_i\ge1-{\displaystyle \sum_{i\in I}^{1} x_i}$$

When $I$ has $0$ element, $${\displaystyle \prod_{i\in I}^{0} (1-x_i)}=1$$ Looking at RHS, $$1-{\displaystyle \sum_{i\in I}^{0} x_i}=1$$ Then $${\displaystyle \prod_{i\in I}^{0} (1-x_i)}\ge1-{\displaystyle \sum_{i\in I}^{0} x_i}$$ Assume ${\displaystyle \prod_{i\in I}^{k} (1-x_i)}\ge1-{\displaystyle \sum_{i\in I}^{k} x_i}$.
When $I$ has $k+1$ elements, $${\displaystyle \prod_{i\in I}^{k+1} (1-x_i)}$$ $$=(1-x_{k+1}){\displaystyle \prod_{i\in I}^{k} (1-x_i)}$$ $$\ge(1-x_{k+1})(1-{\displaystyle \sum_{i\in I}^{k} x_i})$$ Looking at RHS, $$1-{\displaystyle \sum_{i\in I}^{k+1} x_i}$$ $$=1-{\displaystyle \sum_{i\in I}^{k} x_i}-x_{k+1}$$ $$=1-x_{k+1}-{\displaystyle \sum_{i\in I}^{k} x_i}$$ $$=(1-x_{k+1})(1-\frac{{\displaystyle \sum_{i\in I}^{k} x_i}}{1-x_{k+1}})$$ Since $1\ge1-x_{k+1}$, $$1-\frac{{\displaystyle \sum_{i\in I}^{k} x_i}}{(1)}\ge1-\frac{{\displaystyle \sum_{i\in I}^{k} x_i}}{(1-x_{k+1})}$$ $$(1-x_{k+1})(1-{\displaystyle \sum_{i\in I}^{k} x_i})\ge(1-x_{k+1})(1-\frac{{\displaystyle \sum_{i\in I}^{k} x_i}}{1-x_{k+1}})$$ $${\displaystyle \prod_{i\in I}^{k+1} (1-x_i)}\ge1-{\displaystyle \sum_{i\in I}^{k+1} x_i}$$ In the problem, given ${\displaystyle \sum_{i\in I}^{k+1} x_i}\le1/3$, $${\displaystyle \prod_{i\in I}^{k+1} (1-x_i)}\ge1-(1/3)$$ Then $$(1-x_1)(1-x_2)\cdot\ldots\cdot(1-x_k)(1-x_{k+1})\ge2/3$$

Answer 1

I will demonstrate how we can go from $n=2$ to $n=3$ and that should tell you how you can go from any $n$ to $n+1$. The assumption now is $x_1+x_2 \leq \frac1 3, x_1,x_2 >0$ implies $(1-x_1)(1-x_2) \geq \frac 2 3$.

Let $x_1+x_2+x_3 \leq \frac1 3, x_1,x_2,x_3 >0$. Then, applying the case $n=2$ to the number $x_1,x_2+x_3$ we get $(1-x_1)(1-x_2-x_3) \geq \frac 2 3$. This can be written as $$(1-x_1) [(1-x_2)(1-x_3)-x_2x_3] \geq \frac2 3 .$$ This means

$$(1-x_1) (1-x_2)(1-x_3)-x_2x_3(1-x_1)(1-x_2) \geq \frac 2 3 .$$ Just transfer $(1-x_1)(1-x_2)x_2x_3$ to the right side to see that $$(1-x_1)(1-x_2)(1-x_3) \geq \frac 2 3. $$

Answer 2

May I suggest a more general related inequality which applies to the particular context of your problem in a very straightforward manner and which is easily proved by induction.

Lemma. Let $I$ be an arbitrary finite set (possibly empty) and $x \in [0, 1]^I$ a family of positive subunitary numbers indexed by $I$. It is then the case that: $$\prod_{i \in I}(1-x_i) \geqslant 1-\sum_{i \in I}x_i.$$ Equality is obtained only when at most one term of the family $x$ is nonzero.

As a note on terminology: to me, ''$t$ is positive'' means $t \geqslant 0$ whereas the strict version $t>0$ I express by saying $t$ is strictly positive.

The inequality is easily proved by induction. Specifically, we are going to prove the following statement:

$$(\forall I)(\forall x)\left(\left(|I|=n \wedge x \in [0,1]^I\right) \Rightarrow \prod_{i \in I}(1-x_i) \geqslant 1-\sum_{i \in I}x_i\right)$$

by induction on $n \in \mathbb{N}$. The base case occurs for $n=0$; since the empty set is the only set of cardinality $0$ and empty products (sums) of real numbers are by definition to $1$ ($0$), the inequality in question is trivially verified (and seen moreover to actually be an equality).

Let us now assume the claim is valid for arbitrary $n \in \mathbb{N}$ and let us prove it holds for $n+1$. To this end let $I$ be an arbitrary index set such that $|I|=n+1$ and let $x \in [0, 1]^I$ be an arbitrary family. Since $n+1 \neq 0$, the set $I$ is necessarily nonempty so we can fix a certain $\alpha \in I$. We also introduce the subset $J=I \setminus \{\alpha\}$ and the restricted family $y=x_{|I}=(x_i)_{i \in J}$.

It is clear that $|J|=n$ and that $y \in [0, 1]^J$, which allows us to apply the induction hypothesis to $J$ and $y$, in order to infer that: $$\prod_{i \in J}(1-y_i) \geqslant 1-\sum_{i \in J}y_i.$$

Keeping in mind that by definition $y_i=x_i$ for every $i \in J$ and that $1-x_{\alpha} \geqslant 0$ (since $x_{\alpha} \leqslant 1$), we multiply the above inequality referring to $y$ by $1-x_{\alpha}$ and obtain:

$$\begin{align*} \prod_{i \in I}(1-x_i)&=(1-x_{\alpha})\prod_{i \in J}(1-x_i)\\ &\geqslant (1-x_{\alpha})\left(1-\sum_{i \in J}x_i\right)\\ &=1-x_{\alpha}-\sum_{i \in J}x_i+x_{\alpha}\sum_{i \in J}x_i \tag{*}\\ &\geqslant 1-\left(x_{\alpha}+\sum_{i \in J}x_i\right)\\ &=1-\sum_{i \in I}x_i, \end{align*}$$ which is precisely the desired inequality referring to family $x$. The last inequality in the sequence above is due to the fact that in the product $x_{\alpha}\displaystyle\sum_{i \in J}x_i$ both factors $x_{\alpha}$ and $\displaystyle\sum_{i \in J}x_i$ are positive -- the latter since it is a sum of positive reals -- and therefore the product is itself positive.

The fact that the case of equality can only occur for families whose support (by which I mean the subset of indices to which correspond nonzero terms of the respective family) is at most a singleton is also justified by induction, along the same format. The base case is trivial and assuming the validity of this necessary (actually equivalent) condition for equality in the case of arbitrary families with index sets of cardinality $n \in \mathbb{N}$, let $x \in [0, 1]^I$, $|I|=n+1$, $\alpha \in I$ and the objects $J$, $y$ be as above.

Since we are now working under the hypothesis that: $$\displaystyle\prod_{i \in I}(1-x_i)=1-\displaystyle\sum_{i \in I}x_i, \tag{**}$$ the chain of inequalities from the above proof must consist only of equalities. In particular, relation $(^*)$ is an equality, which means that $x_{\alpha}\displaystyle\sum_{i \in J}x_i=0$. This relation leads to one of the following two cases:

1. $x_{\alpha}=0$, in which case the original relation of equality $(^{**})$ reduces to the analogous one for family $y$ and by the induction hypothesis the support of $y$ is at most singleton. However, in this case the supports of $x$ and $y$ coincide and thus the claim concerning $x$ follows.
2. $\displaystyle\sum_{i \in J}x_i=0$, which considered in combination with the fact that all the terms $x_i \geqslant 0$ are positive actually forces $x_i=0$ for all $i \in J$. This means that the support of $x$ is included in $\{\alpha\}$ and is therefore at most a singleton.