Prove that $ 1 + \sum_{k=0}^{n-1}(\prod_{j=0}^{k-1}(1+w_j))w_k \leq \prod^{n-1}_{k=0}(1+w_k) $ where $(w_n)$ is a nonnegative sequence.

Question

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.

Answer 1

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.

Answer 2

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$.