Proving that $\sum_{i=1}^n\frac{a_i}{1-a_i}\leq\sum_{i=1}^n\frac{b_i}{1-b_i}$

Question

Suppose $a_1,a_2,...,a_n>0$ and $\sum_{i=1}^na_i=1$. Define $b_1,b_2,...,b_n$ by $b_i=\frac{a_i^2}{\sum_{j=1}^n(a_j^2)}$. Show that $$\sum_{i=1}^n\frac{a_i}{1-a_i}\leq\sum_{i=1}^n\frac{b_i}{1-b_i}$$.

I have been unable to make any substantial progress. I've noticed that $\sum b_i=1$ also. Letting $A_n=\sum_{i=1}^n\frac{a_i}{1-a_i}$, $B_n=\sum_{i=1}^n\frac{b_i}{1-b_i}$, both $A_n$ and $B_n$ are greater than one, and more precisely $B_n\geq\frac{n}{n-1}$. But nothing I've found seems particularly useful.

I found that the problem simplifies to $\sum_{i=1}^n\frac{1}{1-a_i}\leq\sum_{i=1}^n\frac{1}{1-b_i}$, but without further progression.

Can anyone help me solve this question?

Question comes from 2014 Irish Mathematical Olympiad

Answer 1

First, note that $f(x)=\frac{x}{1-x}$ is convex on the interval $(0,1)$.

Also, if you arrange the $a_i$ terms in decreasing order, so the corresponding $b_i$ terms are also in decreasing order, then $(b_1,b_2,\ldots, b_n)$ majorizes $(a_1,a_2,\ldots,a_n)$: that is, for all $1\leq k\leq n$ $$b_1+b_2 +\cdots + b_k \geq a_1 + a_2 + \cdots a_k$$ [Does this step need more elucidation? The largest $k$ squares sum to a larger percentage of the sum of all the squares than the largest $k$ original terms make out of the original sum (with equality when all terms are equal). We could formalize this if needed, but it seems like a digression.]

But then, Karamata's inequality (related to Jensen's inequality see https://en.wikipedia.org/wiki/Karamata%27s_inequality) holds.

A nice reference on inequalities that often come up in olympiads is: http://www.mit.edu/~evanchen/handouts/Ineq/en.pdf

Answer 2

This starts with the observation in my comment above, quoted here:

"Since $\sum_i a_i=\sum_i b_i=1$, we can rewrite the inequality as $\sum_i a_i / ∑_{j\neq i}a_j \leq \sum_i b_i / \sum_{j \neq i} b_j=\sum_i a^2 / \sum_{j \neq i}a^2$. Then since both sides of this are constant under the transformation $a_i, \cdots, a_n \to \lambda a_i, \cdots, \lambda a_n$, it suffices to solve this new inequality without the condition $\sum_i a_i = 1$."

Therefore this problem is equivalent to showing that $f(1) \leq f(2)$, where

$$f(x) = \sum_i \frac{a_i^x}{\sum_{j \neq i}a_j^x}$$

and where we assume that $a_i > 0 \,\forall\, i$ (but not necessarily that $\sum_i a_i = 1$). It is sufficient to show that $f(x)$ is non-decreasing for $x > 0$. We calculate

$$f'(x) = \sum_i \frac{a_i^x \sum_{j \neq i} a_j^x \log \frac{a_i}{a_j}}{( \sum_{j \neq i} a_j^x )^2}$$

Letting $c_{i,x} = \sum_{j \neq i} a_j^x$, we can write this as:

$$f'(x) = \sum_{i \neq j} \frac{ (a_i a_j)^x \log \frac{a_i}{a_j}}{c_{i,x}^2} $$ $$= \sum_{i < j} (a_i a_j)^x \left(\frac{1}{c_{i,x}^2} \log\frac{a_i}{a_j} + \frac{1}{c_{j,x}^2} \log\frac{a_j}{a_i} \right)$$ $$= \sum_{i < j} (a_i a_j)^x \log\frac{a_i}{a_j} \left(\frac{1}{c_{i,x}^2} - \frac{1}{c_{j,x}^2} \right)$$

Assuming without loss of generality that $a_i \leq a_j$, it follows that $c_{i,x} \geq c_{j,x}$, so $\log\frac{a_i}{a_j} \leq 0$, $\frac{1}{c_{i,x}^2} - \frac{1}{c_{j,x}^2} \leq 0$, and thus $\log\frac{a_i}{a_j} \left(\frac{1}{c_{i,x}^2} - \frac{1}{c_{j,x}^2} \right)$ is non-negative. We also know that $(a_i a_j)^x \geq 0$, so therefore each term in the above summation is non-negative, and thus $f'(x) \geq 0$. QED

Answer 3

So what we learn from this problem is that if you have a set of non-negative weights $a_i$, and transform them to another set of weights proportional to $F(a_i)$ then the condition for the function $F$ to produce majorization (of old weights by new weights) is that $F(x)/x$ is increasing. Cool.