6
$\begingroup$

Let $x_1,x_2,\cdots,x_n$ be $n$ non-negative numbers such that $x_1+x_2+\cdots+x_n=1$. Show $$\sum_{i=1}^n \frac{x_i^2}{\sum_{j=1}^i x_j}\ge \frac{2}{n}-\frac{1}{n^2}.$$

We may consider using Cauchy. That is

$$\sum_{i=1}^n\sum_{j=1}^i x_j\cdot \sum_{i=1}^n \frac{x_i^2}{\sum_{j=1}^i x_j}\ge \left(\sum_{i=1}^nx_i\right)^2=1.$$

How to go on?

$\endgroup$
5
  • $\begingroup$ The right-hand side is $1-\left(1-\frac{1}{n}\right)^2$, so maybe subtract the left-hand side from $1=\sum_{i=1}^{n}{x_i}$? This is not a hint, just looking for possible approaches. $\endgroup$ Sep 24, 2022 at 3:50
  • 1
    $\begingroup$ You need $x_1\neq 0$ for the left side of the inequality to even be defined... $\endgroup$ Sep 24, 2022 at 4:12
  • $\begingroup$ it looks like inequality can hold $n=2$ and all variables are equal, otherwise equality is attained in some weird combination. Also, this is a quadratic in $x_n$, so finding the discriminant might directly yield the problem if expanded careful enough. $\endgroup$
    – dezdichado
    Sep 24, 2022 at 4:13
  • 1
    $\begingroup$ if you construct positive variables $a_2, a_3,\dots a_n$ such that you use AM-GM as: $$\dfrac{x_i^2}{x_1+x_2+\dots +x_i}\geq 2a_ix_i- a_i^2(x_1+x_2+\dots +x_i) $$ and then you add all of them together to get the coefficients $\dfrac{2n-1}{n^2}$ in front of each of $x_1,x_2,\dots x_{n-1},$ the coefficient in front of $x_n$ will be larger than $\dfrac{2n-1}{n^2}$, which finishes the problem. But this is a pain the ass to write out in detail. $\endgroup$
    – dezdichado
    Sep 24, 2022 at 4:46
  • 1
    $\begingroup$ FWIW, the lower bound $2/n-1/n^2$ isn't tight when $n \ge 3$. Computing the minimum of the sum over all non-negative $x_i$ that sum to 1 for small $n$ suggests that this minimum is $b_1 = 1$ and $b_n = 1 - (1-b_{n-1}/2)^2$ for all $n > 1$. $\endgroup$
    – Jim Ferry
    Sep 24, 2022 at 7:37

3 Answers 3

2
$\begingroup$

Fact 1: Let $n \ge 2$. Let $x_1, x_2, \cdots, x_n \ge 0$ and $x_1 > 0$. Then $$\sum_{i=1}^n \frac{x_i^2}{\sum_{j=1}^i x_j} \ge \frac{2n - 1}{n^2}(x_1 + x_2 + \cdots + x_n).$$ (The proof is given at the end.)

By Fact 1, we are done.


Proof of Fact 1:

We use Mathematical Induction.

It is easy to verify the case $n = 2$.

Assume that it is true for $n$.

For $n+1$, by the inductive hypothesis, we have \begin{align*} \sum_{i=1}^{n+1} \frac{x_i^2}{\sum_{j=1}^i x_j} &= \sum_{i=1}^{n} \frac{x_i^2}{\sum_{j=1}^i x_j} + \frac{x_{n+1}^2}{\sum_{j=1}^{n+1} x_j}\\ &\ge \frac{2n - 1}{n^2}(x_1 + x_2 + \cdots + x_n) + \frac{x_{n+1}^2}{\sum_{j=1}^{n+1} x_j}. \end{align*} It suffices to prove that $$\frac{2n - 1}{n^2}(x_1 + x_2 + \cdots + x_n) + \frac{x_{n+1}^2}{\sum_{j=1}^{n+1} x_j} \ge \frac{2n+1}{(n+1)^2}(x_1 + x_2 + \cdots + x_{n+1}).$$ Since the inequality is homogeneous, assume that $x_1 + x_2 + \cdots + x_n = 1$. Letting $y = x_{n+1}$, it suffices to prove that $$\frac{2n - 1}{n^2} + \frac{y^2}{1+y} \ge \frac{2n+1}{(n+1)^2}(1 + y)$$ or $$n^4y^2 + (-2n^3 + n^2 - 1)y + 2n^2 - 1 \ge 0$$ which is true (easy).

We are done.

$\endgroup$
7
  • $\begingroup$ +1. I was thinking exactly this once I realized the whole thing is a quadratic in $x_n.$ $\endgroup$
    – dezdichado
    Sep 24, 2022 at 20:48
  • 1
    $\begingroup$ @dezdichado Thanks. For your idea in comment, we can obtain $a_2 = 1/2$, $a_{i+1} = \frac12f(a_i)$ for $i=2, 3, \cdots, n-2$, and $a_n = \sqrt{f(a_{n-1}) - (2n-1)/n^2}$ where $f(u) = 2u - u^2$. Perhaps there are no closed form. $\endgroup$
    – River Li
    Sep 24, 2022 at 23:21
  • $\begingroup$ yeah for $n=3,4$ I manually checked but there was no closed form for the last $a_n$ $\endgroup$
    – dezdichado
    Sep 24, 2022 at 23:31
  • 1
    $\begingroup$ @dezdichado Also, I evaluated the minimum for small $n$ in which the minimum is attained when $\frac{x_2}{x_1} \approx 1$, $\frac{x_{k+1}}{x_k} \approx \frac{k+4}{k+3}$ for $k=2, 3, \cdots, n-1$, that is $x_1 \approx \frac{10}{n^2+7n+2}$ and $x_k = \frac{2(k+3)}{n^2+7n+2}$ for $k\ge 2$. Not sure if it is the case for large $n$. $\endgroup$
    – River Li
    Sep 24, 2022 at 23:32
  • 1
    $\begingroup$ @dezdichado For $n=3, 4$, all $a_i$'s should be found in closed form, right? Do you do something like $$\sum_{i=1}^n \frac{x_i^2}{\sum_{j=1}^i x_j} \ge x_1 + \sum_{i=2}^n \left(2y_i x_i - y_i^2 \sum_{j=1}^i x_j\right) =\left(1 - \sum_{i=2}^n y_i^2\right)x_1 + \sum_{k=2}^n \left(2y_k - \sum_{i=k}^n y_i^2\right)x_k?$$ Let $c_i$ be the coefficients of $x_i$ for $i=1, 2, \cdots, n$. We do $c_1 - c_2, ~ c_2 - c_3, ~ \cdots, ~ c_{n-1} - c_n$ to solve $a_i$'s. $\endgroup$
    – River Li
    Sep 24, 2022 at 23:37
1
$\begingroup$

We'll assume $x_1>0,$ since the left hand side is undefined if $x_1=0.$ But if ww treat the first term as zero when $x_1=0,$ we can just use that the right side is decreasing on $n.$

Try induction on $n.$ When $n=1,$ you have $x_1=1,$ the inequality becomes $1\geq 1.$

If true for $n,$ take $x_1,\dots,x_{n+1}.$

Since $x_{1}>0,$ then the $x_{n+1}<1.$

Let $y_i=\frac{x_i}{1-x_{n+1}}$ for $i=1,\dots,n.$

Then $\sum_1^n y_i=1,$ so we have:

$$\frac2n-\frac1{n^2}\leq \sum_{i=1}^n \frac{y_i^2}{\sum_{j=1}^i y_j}=\frac1{1-x_{n+1}}\sum_{i=1}^n\frac{x_i^2}{\sum_{j=1}^i x_j}$$

So $$\begin{align}\sum_{i=1}^{n+1}\frac{x_i^2}{\sum_{j=1}^i x_j}&\geq (1-x_{n+1})\left(\frac2n-\frac1{n^2}\right)+x_{n+1}^2\\\end{align}$$

In general, the minimum value for $f(x)=(1-x)a+x^2$ when $0<a\leq 1$ and $x\in [0,1]$ is at $x=a/2$ and the value is $a-\frac{a^2}{4}=1-(1-a/2)^2.$

So this is the recursion for the absolute minimum value of the left hand side:

$$m_1=1, m_{n+1}=\inf_{m\in[m_n,1]}1-(1-m/2)^2=1-(1-m_n/2)^2.$$

Because $1-(1-u/2)^2=u-\frac{u^2}4$ is increasing on $[0,1].$ We have, if $m_n\geq \frac2n-\frac1{n^2}$ then:

$$\begin{align}m_{n+1}&\geq 1-\left(1-\frac 1n+\frac1{2n^2}\right)^2\end{align}$$

Now, $$\frac2{n+1}-\frac1{(n+1)^2}=1-\left(1-\frac1{n+1}\right)^2$$

So you need $$\frac1{n+1}\leq \frac1{n}-\frac1{2n^2}=\frac{2n-1}{2n^2}$$

or $$2n^2\leq (n+1)(2n-1)=2n^2+n-1$$ which is obviously true for $n\geq1.$

$\endgroup$
-1
$\begingroup$

Base Case:- $n=1$ $$\sum_{i=1}^1 \frac{x_i^2}{\sum_{j=1}^i x_j}\ge \frac{2}{1}-\frac{1}{1^2}$$ $$1 \ge 1$$ Thus the base case holds.
Hypothesis:- $$\sum_{i=1}^{n+1} \frac{x_i^2}{\sum_{j=1}^i x_j}\ge \frac{2}{n+1}-\frac{1}{{(n+1)}^2}$$ And now for the step:- $$\sum_{i=1}^n \frac{x_i^2}{\sum_{j=1}^i x_j} + \frac{x_{n+1}^2}{\sum_{j=1}^{n+1} x_j}\ge \frac{2}{n}-\frac{1}{n^2} + \frac{x_{n+1}^2}{\sum_{j=1}^{n+1} x_j}$$ $$\sum_{i=1}^{n+1} \frac{x_i^2}{\sum_{j=1}^i x_j} \ge \frac{2}{n}-\frac{1}{n^2} + \frac{x_{n+1}^2}{1}$$ This is as $x_1+x_2+\cdots+x_n+x_{n+1}=1$
As $n \ge 1$ so:- $$2n^2\ge1$$ $$\Rightarrow 2n(n+1)\ge2n+1$$ $$\Rightarrow 2 \ge \frac{2n+1}{n(n+1)}$$ $$\Rightarrow 2\cdot\left[\frac{1}{n(n+1)}\right] \ge \frac{2n+1}{n^2(n+1)^2}$$ $$\Rightarrow 2\cdot\left[\frac{1}{n} - \frac{1}{n+1}\right]\ge \frac{1}{n^2}-\frac{1}{(n+1)^2}$$ $$\Rightarrow\frac{2}{n}-\frac{1}{n^2}\ge \frac{2}{n+1} -\frac{2}{(n+1)^2} $$ $$\Rightarrow\frac{2}{n}-\frac{1}{n^2} + x_{n+1}^2\ge \frac{2}{n+1} -\frac{1}{(n+1)^2} $$ This is as $x_{n+1}$ is non-negative.
Thus we finally get:- $$\sum_{i=1}^{n+1} \frac{x_i^2}{\sum_{j=1}^i x_j} \ge \frac{2}{n}-\frac{1}{n^2} + x_{n+1}^2\ge \frac{2}{n+1} -\frac{1}{(n+1)^2} $$ completing the step.

$\endgroup$
3
  • 1
    $\begingroup$ "And now for the step..." But $\sum_{i=1}^n x_i<1,$ so you can't use the induction step. Your argument would say that the left side is always more than $1.$ $\endgroup$ Sep 24, 2022 at 13:41
  • $\begingroup$ But how is $\sum_{i=1}^n x_i<1$ as it is given that 'Let $x_1,x_2,⋯,x_n$ be $n$ non-negative numbers such that $x_1+x_2+⋯+x_n=1$' $\endgroup$ Sep 24, 2022 at 16:30
  • $\begingroup$ You are trying to prove it for $n+1,$ so now $\sum_{i=1}^{n+1} x_i=1.$ That means $\sum_{i=1}^n x_i=1$ only when $x_{n+1}=0.$ $\endgroup$ Sep 24, 2022 at 18:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .