Tuesday, June 21, 2011


If $x_1,\dots,x_n$ are real numbers such that $0 \leq x_i \leq 1 \forall i$, and satisfies $x_1 + \dots + x_n = m+r$ where $m$ is an integer and $0 \leq r < 1$, show that:

$$(1+x_1)(1+x_2)\dots(1+x_n) \geq (1+r)2^m$$

Determine the conditions under which equality is achieved.


For each $i$ such that $x_i = 0$ or $x_i = 1$, we can safely eliminate them from the problem without changing neither the condition nor the inequality. So without loss of generality, we can assume that $0 < x_i < 1$ for all $i$.

Now, we prove by induction on $n$. It is trivial for $n=1$. For $n=2$, we have two cases:
1. The simple case, $x_1 + x_2 = r < 1$ then the inequality also holds trivially
2. The overflowing case, where $1 < x_1 + x_2 = 1 + r$, then:
$$(1-x_1)(1-x_2) \geq 0$$
$$\iff 1+x_1x_2 \geq x_1+x_2 = 1+r$$
$$\iff 1+x_1+x_2+x_1x_2 \geq 2+2r$$
$$\iff (1+x_1)(1+x_2) \geq 2(1+r)$$

Now, for a larger value of $n$, suppose that the inequality is established for $n-1$, and suppose that $x_1 + \dots + x_{n-1} = m + r$. Again we have two cases,

1. The simple case, if $x_n + r < 1$ then $x_1 + \dots + x_n = m+ (r+x_n) < m+1$
$$(1+x_1)\dots(1+x_{n-1})(1+x_n) \geq (1+x_n)(1+r)2^m \geq (1+r+x_n)2^m$$
which follows from the simple case for $n=2$ above.

2. The overflowing case, if $1 < x_n + r = 1 + r_2$ then $x_1 + \dots + x_n = (m+1) + r_2$

$$(1+x_1) \dots (1+x_{n-1})(1+x_n) \geq (1+x_n)(1+r)2^m$$
$$ \geq (1+r_2)2^{m+1}$$
which is similar to the overflowing case from $n=2$ above.

The equality cases can be determined as follows:
If all $x_i$s are zeros or ones, then the equality follows trivially. We assert then at most one of the $x_i$s are strictly between zero and one. Because if there are two of them, then both the simple case and the overflowing case in $n=2$ will never reach equality. The inductive step in the proof also depends on these two cases.

No comments:

Post a Comment