Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Any idea? Any helpful trick?

Thank you.

share|improve this question
1  
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

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.