# Proof inequality

I can't proof this inequality. $$1 + \sum_{k=0}^{n-1}\biggl(\prod_{j=0}^{k-1}(1+w_j)\biggr)w_k \leq \prod^{n-1}_{k=0}(1+w_k)$$ where $(w_n)$ is a nonnegative sequence.

Thank you.

-
take $w_j=-1$ for all $j$ and the righthand side is 0, the left hand side is 1, you must have forgot something – Dominic Michaelis Mar 3 '13 at 20:07
@DominicMichaelis Sorry... (w_n) is a nonnegative sequence... – R. M. Mar 3 '13 at 20:08
you messed up with the index on the right hand side or? the k=0 should be below – Dominic Michaelis Mar 3 '13 at 20:11
@DominicMichaelis Of course I messed up, sorry again. – R. M. Mar 3 '13 at 20:13
@DominicMichaelis Because of the empty product, when $w_j=-1$ for all $j$ the left hand side is $1+w_0=1+(-1)=0$. No problem! – Byron Schmuland Mar 3 '13 at 21:32

Prove it by induction. For $n=1$, $$1 \leq 1 + w_0$$

For $n=2$, $$1 + (1 + w_0)w_1 \leq (1 + w_0)(1 + w_1)$$

Suppose it's true for $n-1$, that is, suppose $$1 + \sum_{k=0}^{n-1} \prod_{j=0}^{k-1}(1 + w_j) w_k \leq \prod_{k=0}^{n-1}(1 + w_k)$$

Then

$$1 + \sum_{k=0}^{n} \prod_{j=0}^{k-1}(1 + w_j) w_k = \color{red}{1 + \sum_{k=0}^{n-1} \prod_{j=0}^{k-1}(1 + w_j) w_k} + \prod_{j=0}^{n-1}(1 + w_j)w_n$$ $$\leq \color{red}{\prod_{k=0}^{n-1}(1+w_k)} + \prod_{j=0}^{n-1}(1 + w_j)w_n = (1 + w_n) \prod_{j=0}^{n-1}(1 + w_j) = \prod_{k=0}^n(1 + w_k)$$

The red expressions are where the inductive hypothesis is used.

-
Thank you! But I don't see easily where your inequality comes from... Can you be more specific please? (Ps: as we have k-1, it's ok to start from k=0?) – R. M. Mar 3 '13 at 21:03
OK, stay tuned for an edit expanding the steps a bit – muzzlator Mar 3 '13 at 21:04
PERFECT! Thank you very much! – R. M. Mar 3 '13 at 21:17

Because of the empty product, the $k=0$ term on the left hand side is $w_0$. We rewrite the left hand side as $$1+w_0+(1+w_0)\sum_{k=1}^{n-1}\left(\prod_{j=1}^{k-1}(1+w_j)\right)w_k=(1+w_0)\left[1 + \sum_{k=1}^{n-1}\biggl(\prod_{j=1}^{k-1}(1+w_j)\biggr)w_k\right].$$ Continuing in this way we find that $$1 + \sum_{k=0}^{n-1}\biggl(\prod_{j=0}^{k-1}(1+w_j)\biggr)w_k = \prod^{n-1}_{k=0}(1+w_k).$$

We have equality for any values $w_j$, whether positive or not.

Added: This equation is not hard to understand. If you expand the right hand side, you get the sum of all possible products of the $w$ variables, including the empty product "$1$". The left hand side is the same sum, grouping together those products whose largest index is $k$.

-