7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $\dfrac{a_i}{1-a_i}=a_i+{a_i}^2+{a_i}^3+\ldots$ might help $\endgroup$ – Marconius Aug 9 '15 at 20:45
  • $\begingroup$ Maybe this will help : ${b}_{i} = {{a}_{i}}^{2}$ $\endgroup$ – Oussama Boussif Aug 9 '15 at 20:45
  • $\begingroup$ Oussama Boussif, how is that so? In the denominator we have $\sum (a_i^2)$, not $(\sum a_i)^2$, in case that is where you got your result. $\endgroup$ – Cataline Aug 9 '15 at 20:49
  • $\begingroup$ Ah my bad I didn't even see that ² :p $\endgroup$ – Oussama Boussif Aug 9 '15 at 20:52
  • $\begingroup$ There is equality between the $a_i$ and $b_i$ and hence the "a" and "b" sums when $a_1=a_2=\cdots=a_n=\frac{1}{n}$ $\endgroup$ – Marconius Aug 11 '15 at 0:26
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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