Some help needed with this induction proof

296 Views Asked by At

Let $x_1, \cdots, x_n, y_1, \cdots, y_n \in \mathbb{R}$ with $0 \leq x_i \leq 1$ and $y_i \geq 0$. We have to show that

$$\frac{(1-x_1)\cdots(1-x_n)}{(1+y_1)\cdots(1+y_n)} \geq 1 - \sum_{i=1}^n x_i - \sum_{i=1}^n y_i$$

I have proved this by using induction. Since $0 \leq x_i \leq 1$ we have $0 \leq 1 - x_i \leq 1$ and since $1 + y_i \geq 1$ we can ultimately get $0 \leq \frac{1 - x_i}{1 + y_i} \leq 1$ which, in return, gives us $0 \geq -\frac{1-x_i}{1 + y_i} \geq -1$

Now for my induction step I have (as always) assumed that the property holds for $n-1$. So we consider

$$\frac{(1-x_1)\cdots(1-x_n)}{(1+y_1)\cdots(1+y_n)} \geq \biggl(1 - \sum_{i=1}^{n-1} x_i - \sum_{i=1}^{n-1} y_i\biggr)\biggl(\frac{1 - x_n}{1 + y_n}\biggr) = \biggl(\sum_{i=1}^{n-1} x_i + \sum_{i=1}^{n-1} y_i - 1\biggr)\biggl(-\frac{1 - x_n}{1 + y_n}\biggr) \geq \biggl(\sum_{i=1}^{n-1} x_i + \sum_{i=1}^{n-1} y_i - 1\biggr)\cdot (-1) = \biggl(1 - \sum_{i=1}^{n-1} x_i - \sum_{i=1}^{n-1} y_i\biggr) \geq 1 - \sum_{i=1}^{n-1} x_i - \sum_{i=1}^{n-1} y_i - x_n - y_n = 1 - \sum_{i=1}^n x_i - \sum_{i=1}^n y_i$$

However, somehow I think that this is not a very appropriate approach for my induction step and it also feels a little bit cheap the way I do it. Take for example $y_1 = y_2 = \cdots = y_{n-1} = 0 = x_{n-1} = \cdots = x_1$, then the second inequality doesn't make any sense. Could anybody maybe help me with that?

2

There are 2 best solutions below

0
On BEST ANSWER

Induction

For $0\le x_j\le1$, we wish to show $$ \prod_{j=1}^n(1-x_j)\ge1-\sum_{j=1}^nx_j\tag1 $$ Proof: $(1)$ is trivial for $n=0$ (the empty product is $1$ and the empty sum is $0$). Suppose $(1)$ holds for $n-1$, then $$ \begin{align} \prod_{j=1}^n(1-x_j) &=(1-x_n)\prod_{j=1}^{n-1}(1-x_j)\tag{2a}\\ &\ge(1-x_n)\left(1-\sum_{j=1}^{n-1}x_j\right)\tag{2b}\\ &=1-\sum_{j=1}^nx_j+x_n\sum_{j=1}^{n-1}x_j\tag{2c}\\ &\ge1-\sum_{j=1}^nx_j\tag{2d} \end{align} $$ Explanation:
$\text{(2a):}$ bring $1-x_n$ out of the product
$\text{(2b):}$ apply $(1)$ for $n-1$
$\text{(2c):}$ expand the product
$\text{(2d):}$ $x_n\sum\limits_{j=1}^{n-1}x_j\ge0$

$(2)$ shows that $(1)$ holds for $n$. Therefore, by induction, $(1)$ holds for all $n\ge0$.

$\large\square$


Application $$ \begin{align} \prod_{j=1}^n\frac{1-x_j}{1+y_j} &=\prod_{j=1}^n(1-x_j)\left(1-\frac{y_j}{1+y_j}\right)\tag{3a}\\ &\ge1-\sum_{j=1}^nx_j-\sum_{j=1}^n\frac{y_j}{1+y_j}\tag{3b}\\ &\ge1-\sum_{j=1}^nx_j-\sum_{j=1}^ny_j\tag{3c} \end{align} $$ Explanation:
$\text{(3a):}$ $\frac1{1+y_j}=1-\frac{y_j}{1+y_j}$
$\text{(3b):}$ apply $(1)$ where $0\le\frac{y_j}{1+y_j}\lt1$ when $y_j\ge0$
$\text{(3c):}$ $\frac{y_j}{1+y_j}\le y_j$ when $y_j\ge0$

0
On

I think you've assumed that $-1+\sum x_i + y_i \geq 0$ in your second inequality. Indeed, it's basically (assuming $y_n=0$ for simplicity) just the statement $$ -1 \leq -(1-x_n) \Rightarrow -(-1+\sum x_i + y_i) \leq -(1-x_n) (-1+\sum x_i + y_i)$$