Thursday, November 19, 2009

3 Sequence Inequality

If $a_i, b_i, c_i$ are sequences of positive numbers for $i = 1,2,\cdots,n$, prove the following inequality:

$\sum (a_i+b_i+c_i) \sum \frac{a_ib_i + b_ic_i+ c_ia_i}{a_i+b_i+c_i} \sum \frac{a_ib_ic_i}{a_ib_i + b_ic_i+ c_ia_i} \leq \sum a_i \sum b_i \sum c_i$

where all summations are taken from $i=1$ to $i=n$. When does equality happen?


First, we prove the following lemma:

$\sum \frac{x_iy_i}{x_i+y_i} \sum (x_i+y_i) \leq \sum x_i \sum y_i$


Let $X = \sum x_i, Y = \sum y_i$. We first note that $(\frac{x_i}{X^2} + \frac{y_i}{Y^2})(\frac{1}{x_i} + \frac{1}{y_i}) \geq (\frac{1}{X} + \frac{1}{Y})^2$ for each $i$.

Which means

$\displaystyle \frac{x_i}{X^2} + \frac{y_i}{Y^2} \geq \frac{1}{1/x_i + 1/y_i}(1/X+1/Y)^2 = \frac{x_iy_i}{x_i+y_i}(1/X+1/Y)^2$

Then, if we let $S = \frac{XY}{X+Y} \iff 1/S = 1/X+1/Y$, then

$\displaystyle \frac{x_i}{X^2} + \frac{y_i}{Y^2} \geq \frac{x_iy_i}{(x_i+y_i)S^2}$

The above inequality holds for all $i$, so we sum them from $i=1$ to $n$ to yield:

$\displaystyle \frac{X}{X^2} + \frac{Y}{Y^2} \geq \sum \frac{x_iy_i}{(x_i+y_i)S^2}$

But the LHS is just $1/X+1/Y = 1/S$, so the last inequality is equivalent to the lemma.
Lemma Interpretation

One thing that I was amazed by is that the lemma has such a striking form. If we let $A(x_1,\cdots,x_k)$ be the arithmetic mean of $x_1,\cdots, x_k$, and $H(x_1,\cdots,x_k)$ be its harmonic mean, the lemma can be rewritten as:

$ \displaystyle A(H(x_1,y_1), \cdots, H(x_n,y_n)) \leq H(A(x_1,\cdots,x_n), A(y_1, \cdots, y_n))$

There is such a similarity between this equation and, for example, Cauchy. Because if we let $G$ to denote geometric mean, then Cauchy's inequality can be rewritten as:

$ \displaystyle A(G(x_1,y_1), \cdots, G(x_n,y_n)) \leq G(A(x_1,\cdots,x_n), A(y_1, \cdots, y_n))$.

Furthermore, if we let $M_p(x_1, \cdots, x_n)$ to be the $p$-th power mean, then $A = M_1, G = M_0, H = M_{-1}$.

Minkowski Inequality is $M_p \circ M_1 \leq M_1 \circ M_p$ for $p > 1$.

Holder (and in turn Cauchy) Inequality is $M_1 \circ M_0 \leq M_0 \circ M_1$.

But our lemma is $M_1 \circ M_{-1} \leq M_{-1} \circ M_{1}$.

In general, if $p < q$ are finite real numbers, then $M_p \circ M_q \geq M_q \circ M_p$ with equality happens when the numbers are all zeros or all proportional.
First Inequality

First we shall prove the following inequality. If we let $A = \sum a_i, B = \sum b_i, C = \sum c_i$

$\displaystyle (AB+BC+CA)\sum \frac{a_ib_ic_i}{a_ib_i + b_ic_i + c_ib_i} \leq ABC$

which can be rewritten as:

$\sum \frac{1}{1/a_i + 1/b_i + 1/c_i} \leq \frac{1}{1/A + 1/B + 1/C}$

First let's define a sequence $p_i = \frac{b_ic_i}{b_i + c_i}$ which is equivalent to $1/p_i = 1/b_i + 1/c_i$. Let $P= \sum p_i$

Then using our lemma, we have $P \leq \frac{BC}{B+C} = \frac{1}{1/B + 1/C}$.

Again, using the lemma,

$LHS = \sum \frac{1}{1/a_i + 1/p_i} \leq \frac{1}{1/A + 1/P} \leq \frac{1}{1/A+1/B+1/C}$ which proves the first inequality.
Second Inequality

Now we shall prove the following inequality.

$\displaystyle (A+B+C)\sum \frac{a_ib_i + b_ic_i + c_ib_i}{a_i+b_i+c_i} \leq AB+BC+CA$

Now let $q_i = b_i + c_i$, so if we let $Q = \sum q_i = B+C$, by the lemma:

$\sum \frac{a_ib_i + a_ic_i}{a_i+b_i+c_i} = \sum \frac{a_i q_i}{a_i + q_i} \leq \frac{AQ}{A+Q} = \frac{AB+AC}{A+B+C}$.


$\displaystyle \sum \frac{b_ic_i + a_ib_i}{a_i+b_i+c_i} \leq \frac{BC+AB}{A+B+C}$.

$\displaystyle \sum \frac{a_ic_i + b_ic_i}{a_i+b_i+c_i} \leq \frac{AC+BC}{A+B+C}$.

Adding three inequalities gives us the second inequality.

When we multiple first and second inequalities, we get the desired result.

No comments:

Post a Comment